The trafic on the Internet is increasing these days due to smartphones. The wireless carriers have to enhance their network infrastructure.

The network of a wireless carrier consists of a number of base stations and lines. Each line connects two base stations bi-directionally. The bandwidth of a line increases every year and is given by a polynomial f(x) of the year x.

Your task is, given the network structure, to write a program to calculate the maximal bandwidth between the 1-st and N-th base stations as a polynomial of x.



Input

The input consists of multiple datasets. Each dataset has the following format:

N M
u1 v1 p1
...
uM vM pM


The first line of each dataset contains two integers N (2 ≤ N ≤ 50) and M (0 ≤ M ≤ 500), which indicates the number of base stations and lines respectively. The following M lines describe the network structure. The i-th of them corresponds to the i-th network line and contains two integers ui and vi and a polynomial pi. ui and vi indicate the indices of base stations (1 ≤ ui, vi ≤ N); pi indicates the network bandwidth.

Each polynomial has the form of:

aLxL + aL-1xL-1 + ... + a2x2 + a1x + a0

where L (0 ≤ L ≤ 50) is the degree and ai's (0 ≤ i ≤ L, 0 ≤ ai ≤ 100) are the coefficients. In the input,

* each term aixi (for i ≥ 2) is represented as <ai>x^<i>
* the linear term (a1x) is represented as <a1>x;
* the constant (a0) is represented just by digits;
* these terms are given in the strictly decreasing order of the degrees and connected by a plus sign ("+");
* just like the standard notations, the <ai> is omitted if ai = 1 for non-constant terms;
* similarly, the entire term is omitted if ai = 0 for any terms; and
* the polynomial representations contain no space or characters other than digits, "x", "^", and "+".



For example, 2x2 + 3x + 5 is represented as 2x^2+3x+5; 2x3 + x is represented as 2x^3+x, not 2x^3+0x^2+1x+0 or the like. No polynomial is a constant zero, i.e. the one with all the coefficients being zero.

The end of input is indicated by a line with two zeros. This line is not part of any dataset.

Output

For each dataset, print the maximal bandwidth as a polynomial of x. The polynomial should be represented in the same way as the input format except that a constant zero is possible and should be represented by "0" (without quotes).

Example

Input

3 3
1 2 x+2
2 3 2x+1
3 1 x+1
2 0
3 2
1 2 x
2 3 2
4 3
1 2 x^3+2x^2+3x+4
2 3 x^2+2x+3
3 4 x+2
0 0


Output

2x+3
0
2
x+2
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

vi& operator+=(vi &a, const vi &b){
	while(a.size() < b.size()) a.pb(0);
	rep(i, min(a.size(), b.size())) a[i] += b[i];
	while(a.size() && a.back() == 0) a.pop_back();
	return a;
}
vi& operator-=(vi &a, const vi &b){
	while(a.size() < b.size()) a.pb(0);
	rep(i, min(a.size(), b.size())) a[i] -= b[i];
	while(a.size() && a.back() == 0) a.pop_back();
	return a;
}
vi min(const vi &a, const vi &b){
	for(int i = max(a.size(), b.size()) - 1; i >= 0; i--)
	if((i < a.size() ? a[i] : 0) != (i < b.size() ? b[i] : 0))
	return (i < a.size() ? a[i] : 0) < (i < b.size() ? b[i] : 0) ? a : b;
	return b;
}

struct flowGraph{
	struct edge{
		int to, rev; 
		vi cap;
		edge(int to, const vi &c, int rev) : to(to), rev(rev){
			cap = c;
		}
	};
	
	int n, *level, *iter;
	vector<vector<edge> > G;
	
	flowGraph(int sz) : n(sz){
		G.resize(n);
		iter = new int[n]; level = new int[n];
	}
	~flowGraph(){
		delete iter; delete level;
	}
	
	void add(int s, int t, const vi &cap){
		G[s].pb(edge(t, cap, G[t].size()));
		G[t].pb(edge(s, vi(0), G[s].size() - 1));
	}
	
	void bfs(int s){
		rep(i, n) level[i] = -1;
		queue<int> q;
		level[s] = 0;
		q.push(s);
		while(!q.empty()){	
			int v = q.front();
			q.pop();
			rep(i, G[v].size()){
				edge &e = G[v][i];
				if(e.cap.size() && level[e.to] < 0){
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}
	
	vi dfs(int v, int t, vi f){
		if(v == t) return f;
		for(int &i = iter[v]; i < (int)G[v].size(); i++){
			edge &e = G[v][i];
			if(e.cap.size() && level[v] < level[e.to]){
				vi d = dfs(e.to, t, min(f, e.cap));
				if(d.size()){
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return vi(0);
	}
	vi max_flow(int s, int t){
		vi flow;
		while(1){
			bfs(s);
			if(level[t] < 0) return flow;
			rep(i, n) iter[i] = 0;
			vi f;
			while((f = dfs(s, t, vi(51, inf))).size()) flow += f;
		}
	}
};
vi parse(string s){
	each(i, s) if(*i == '+') *i = ' ';
	stringstream ss(s);
	vi v;
	while(ss >> s){
		int p, e = s.find("x") != s.npos;
		if((p = s.find("^")) != s.npos){
			e = atoi(s.substr(p + 1).c_str());
		}
		while(v.size() <= e) v.pb(0);
		
		if((p = s.find("x")) != s.npos) s = s.substr(0, p);
		if(s == "") s += "1";
		v[e] = atoi(s.c_str());
	}
	return v;
}
int main(){
	int n, m;
	while(cin >> n >> m, n){
		flowGraph g(n);
		rep(i, m){
			int a, b;
			string c;
			cin >> a >> b >> c;
			a--; b--;
			vi v = parse(c);
			g.add(a, b, v);
			g.add(b, a, v);
		}
		vi ans = g.max_flow(0, n - 1);
		if(ans.empty()){
			cout << 0 << endl;
			continue;
		}
		
		for(int i = ans.size() - 1; i >= 0; i--){
			if(ans[i] == 0) continue;
			if(i < ans.size() - 1) cout << "+";
			if(ans[i] != 1 || i == 0) cout << ans[i];
			if(i > 0) cout << "x";
			if(i > 1) cout << "^" << i;
		}
		cout << endl;
	}
	return 0;
}