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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define min(x,y) (x<y?x:y)
using namespace std;
using namespace rel_ops;
typedef vector<int> poly;
const int MX=50;			//max deg
int deg(poly x){
	for(int i=MX;i>=0;i--) if(x[i]!=0) return i;
	return -1;
}
bool operator<(poly x,poly y){
	for(int i=MX;i>=0;i--){
		if(x[i]<y[i]) return 1;
		if(x[i]>y[i]) return 0;
	}
	return 0;
}
bool operator>(poly x,poly y){return (y<x);}
poly operator+(poly x,poly y){
	rep(i,MX+1) x[i]+=y[i];
	return x;
}
poly operator-(poly x,poly y){
	rep(i,MX+1) x[i]-=y[i];
	return x;
}
void operator+=(poly &x,poly y){
	rep(i,MX+1) x[i]+=y[i];
}
void operator-=(poly &x,poly y){
	rep(i,MX+1) x[i]-=y[i];
}
poly operator*(poly x,poly y){
	poly z(MX+1,0);
	rep(i,MX+1) rep(j,MX+1-i) z[i+j]+=x[i]*y[j];
	return z;
}
poly operator*(int x,poly y){
	rep(i,MX+1) y[i]*=x;
	return y;
}
void showpoly(poly x){
	int N=deg(x);
	if(N==-1){
		puts("0");
		return;
	}
	for(int i=N;i>=0;i--){
		if(x[i]==0) continue;
		if(i!=N&&x[i]>0) cout<<"+";
		if(x[i]==-1) cout<<"-";
		else if(x[i]!=1) cout<<x[i];
		if(i==0){
			if(x[i]==1||x[i]==-1) cout<<"1";
		}else if(i==1){
			cout<<"x";
		}else{
			cout<<"x^"<<i;
		}
	}
	puts("");
}
int num(string &s,int &it){
	int n=1;
	if(s[it]=='-'){
		it++;
		n=-1;
	}
	int x=0;
	while(isdigit(s[it])){
		x=x*10+s[it++]-'0';
	}
	return x*n;
}
poly term(string &s,int& it){
	int c=1;
	int d=0;
	if(isdigit(s[it])||s[it]=='-') c=num(s,it);
	if(s[it]=='x'){
		it++;
		d=1;
		if(s[it]=='^'){
			it++;
			d=num(s,it);
		}
	}
	poly ret(MX+1);
	ret[d]=c;
	return ret;
}
poly sttopoly(string s){
	s+="$";
	int it=0;
	poly ret=term(s,it);
	while(s[it]=='+'||s[it]=='-'){
		if(s[it]=='+'){
			it++;
			ret=ret+term(s,it);
		}else{
			it++;
			ret=ret-term(s,it);
		}
	}
	return ret;
}

typedef poly D;
struct edge {
	int to;
	D cap;
	int rev;
	edge(int to,D cap,int rev) :to(to),cap(cap),rev(rev){}
};
const int MAX_V=50;
D inf(51),zero(51);
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];
void add_edge(int from, int to, D cap){
	edge e1(to,cap,G[to].size()),e2(from,cap,G[from].size());
	G[from].push_back(e1);
	G[to].push_back(e2);
}
void bfs(int s){
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s]=0;
	que.push(s);
	while(!que.empty()){
		int v=que.front();
		que.pop();
		for(edge& e:G[v]){
			if(e.cap>zero && level[e.to]<0){
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}
D dfs(int v,int t,D f){
//	cout<<v<<"v"<<endl;
	if(v==t) return f;
	for(int &i=iter[v];i<G[v].size();i++){
		edge &e=G[v][i];
		if(e.cap>zero && level[v]<level[e.to]){
			// cout<<"f=";
			// showpoly(f);
			// cout<<"e.cap=";
			// showpoly(e.cap);
			// cout<<"min=";
			// showpoly(min(f,e.cap));
			// bool b=(f<e.cap);
			// show(b);
			D d=dfs(e.to,t,min(f,e.cap));
			if(d>zero){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return zero;
}
D max_flow(int s,int t){
	D flow=zero;
	while(true){
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter,0,sizeof(iter));
		D f=zero;
		while( (f=dfs(s,t,inf))>zero ) flow+=f;
	}
}
int main(){
	inf[50]=100000000;
	while(true){
		int N,M;
		cin>>N>>M;
		if(N==0) break;
		rep(i,N) G[i].clear();
		rep(i,M){
			int x,y;
			string s;
			cin>>x>>y>>s;
			add_edge(x-1,y-1,sttopoly(s));
		}
		showpoly(max_flow(0,N-1));
	}
}