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<cctype>
#include<cstdio>
#include<vector>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef vector<int> polynomial;

const polynomial ZERO(51,0);

void operator+=(polynomial &p,const polynomial &q){ rep(i,51) p[i]+=q[i]; }
void operator-=(polynomial &p,const polynomial &q){ rep(i,51) p[i]-=q[i]; }

polynomial operator-(const polynomial &p,const polynomial &q){
	polynomial r=p;
	rep(i,51) r[i]-=q[i];
	return r;
}

polynomial parse(const char *s){
	polynomial p(51);
	int len=strlen(s),a=0;
	rep(i,len+1){
		if(i==len || s[i]=='x'){
			if(a==0) a=1; // 係数 1 が省略されていた
			int e=0;
			if(s[i]=='x'){
				i++;
				if(s[i]!='^'){
					e=1;
				}
				else{
					i++;
					for(;isdigit(s[i]);i++) e=e*10+(s[i]-'0');
				}
			}
			p[50-e]=a;
			a=0;
		}
		else{
			a=10*a+(s[i]-'0');
		}
	}
	return p;
}

void print(const polynomial &p){
	bool b=false;
	rep(i,51) if(p[i]>0) {
		int e=50-i;
		if(b) putchar('+');
		if(p[i]>1 || e==0) printf("%d",p[i]);
		if(e>=1) putchar('x');
		if(e>=2) printf("^%d",e);
		b=true;
	}
	puts(b?"":"0");
}

const int V_MAX=50;
const int E_MAX=500;

template<class T>
struct graph{
	int n,m,head[V_MAX],next[2*E_MAX],to[2*E_MAX];
	T capa[2*E_MAX],flow[2*E_MAX];

	void init(int N){
		n=N;
		m=0;
		rep(u,n) head[u]=-1;
	}

	void add_undirected_edge(int u,int v,T ca){
		next[m]=head[u]; head[u]=m; to[m]=v; capa[m]=ca; flow[m]=ZERO; m++;
		next[m]=head[v]; head[v]=m; to[m]=u; capa[m]=ca; flow[m]=ZERO; m++;
	}
};

const polynomial INF(51,1<<29);

int layer[V_MAX],now[V_MAX];

template<class T>
bool make_layer(const graph<T> &G,int s,int t){
	int n=G.n;
	rep(u,n) layer[u]=(u==s?0:-1);

	int head=0,tail=0;
	static int Q[V_MAX]; Q[tail++]=s;
	while(head<tail && layer[t]==-1){
		int u=Q[head++];

		for(int e=G.head[u];e!=-1;e=G.next[e]){
			int v=G.to[e];
			T capa=G.capa[e],flow=G.flow[e];

			if(capa-flow>ZERO && layer[v]==-1){
				layer[v]=layer[u]+1;
				Q[tail++]=v;
			}
		}
	}

	return layer[t]!=-1;
}

template<class T>
T augment(graph<T> &G,int u,int t,T water){
	if(u==t) return water;

	for(int &e=now[u];e!=-1;e=G.next[e]){
		int v=G.to[e];
		T capa=G.capa[e],flow=G.flow[e];

		if(capa-flow>ZERO && layer[v]>layer[u]){
			T w=augment(G,v,t,min(water,capa-flow));
			if(w>ZERO){
				G.flow[ e ]+=w;
				G.flow[e^1]-=w;
				return w;
			}
		}
	}
	return ZERO;
}

template<class T>
T Dinic(graph<T> &G,int s,int t){
	int n=G.n;
	T ans=ZERO;
	while(make_layer(G,s,t)){
		rep(u,n) now[u]=G.head[u];
		for(T water(51,1);water>ZERO;ans+=water) water=augment(G,s,t,INF);
	}
	return ans;
}

int main(){
	for(int n,m;scanf("%d%d",&n,&m),n;){
		graph<polynomial> G;
		G.init(n);
		rep(i,m){
			int u,v;
			char s[512]; scanf("%d%d%s",&u,&v,s); u--; v--;
			G.add_undirected_edge(u,v,parse(s));
		}
		print(Dinic(G,0,n-1));
	}
	return 0;
}