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<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int D_MAX_V=102;
const int D_v_size=102;
struct D_wolf{
	int t,c,r;
	D_wolf(){t=c=r=0;}
	D_wolf(int t1,int c1,int r1){
		t=t1;c=c1;r=r1;
	}
};
vector<D_wolf>D_G[D_MAX_V];
vector<int>D_sub[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];

void add_edge(int from,int to,int cap){
	D_G[from].push_back(D_wolf(to,cap,D_G[to].size()));
	D_sub[from].push_back(1);
	D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1));
	D_sub[to].push_back(0);
}
void D_bfs(int s){
	for(int i=0;i<D_v_size;i++)D_level[i]=-1;
	queue<int> Q;
	D_level[s]=0;
	Q.push(s);
	while(Q.size()){
		int v=Q.front();
		Q.pop();
		for(int i=0;i<D_G[v].size();i++){
			if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){
				D_level[D_G[v][i].t]=D_level[v]+1;
				Q.push(D_G[v][i].t);
			}
		}
	}
}
int D_dfs(int v,int t,int f){
	if(v==t)return f;
	for(;D_iter[v]<D_G[v].size();D_iter[v]++){
		int i=D_iter[v];
		if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){
			int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c));
			if(d>0){
				D_G[v][i].c-=d;
				D_G[D_G[v][i].t][D_G[v][i].r].c+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		D_bfs(s);
		if(D_level[t]<0)return flow;
		for(int i=0;i<D_v_size;i++)D_iter[i]=0;
		int f;
		while((f=D_dfs(s,t,99999999))>0){flow+=f;}
	}
	return 0;
}
int g[60][60][60];
int res[60];
char in[1000];
int cur;
int val[60];
pair<int,int>fact(){
	int tmp=0;
	while('0'<=in[cur]&&in[cur]<='9'){
		tmp*=10;tmp+=in[cur]-'0';cur++;
	}
	if(tmp==0)tmp=1;
	if(in[cur]!='x')return make_pair(0,tmp);
	cur++;
	if(in[cur]!='^')return make_pair(1,tmp);
	cur++;
	int t2=0;
	while('0'<=in[cur]&&in[cur]<='9'){
		t2*=10;t2+=in[cur]-'0';cur++;
	}
	return make_pair(t2,tmp);
}
void expr(){
	pair<int,int> tmp=fact();
	val[tmp.first]+=tmp.second;
	while(in[cur]=='+'){
		cur++;
		tmp=fact();
		val[tmp.first]+=tmp.second;
	}
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<60;i++)for(int j=0;j<60;j++)for(int k=0;k<60;k++)
			g[i][j][k]=0;
		for(int i=0;i<b;i++){
			int p,q;
			scanf("%d%d%s",&p,&q,in);
			p--;q--;
			cur=0;
			for(int j=0;j<60;j++)val[j]=0;
			expr();
			for(int j=0;j<60;j++)g[j][p][q]=g[j][q][p]=val[j];
		}
		for(int i=59;i>=0;i--){
			for(int j=0;j<D_MAX_V;j++){
				D_G[j].clear();
				D_sub[j].clear();
				D_level[j]=D_iter[j]=0;
			}
			for(int j=0;j<a;j++)for(int k=0;k<a;k++){
				add_edge(j,k,g[i][j][k]);
			}
			res[i]=max_flow(0,a-1);
			for(int j=0;j<a;j++){
				for(int k=0;k<D_G[j].size();k++){
					if(D_sub[j][k]&&D_G[j][k].c){
						for(int l=i-1;l>=0;l--)g[l][j][D_G[j][k].t]=999999999;
					}
				}
			}
		}
		bool yet=true;
		for(int i=59;i>=0;i--){
			if(res[i]==0)continue;
			if(!yet)printf("+");
			yet=false;
			if(i==0||res[i]>1)printf("%d",res[i]);
			if(i)printf("x");
			if(i>1)printf("^%d",i);
		}
		if(yet)printf("0");
		printf("\n");
	}
}