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 MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct edge{
	int to,rev;
	vector<int> cap;
	edge(){}
	edge(int tt,vector<int> cc,int rr){
		to=tt;
		rev=rr;
		cap.resize(cc.size());
		for(int i=0;i<cc.size();i++){
			cap[i]=cc[i];
		}
	}
};

class dinic{
public:
	const int INF=100000;
	vector<edge> G[501];
	int level[501];
	int iter[501];
	void add_edge(int from,int to,vector<int> cap){
		G[from].push_back(edge(to,cap,G[to].size()));
		G[to].push_back(edge(from,cap,G[from].size()-1));
	}

	bool checkemp(vector<int> &cap){
		int s=cap.size();
		for(int i=s-1;i>=0;i--){
			if(cap[i]>0)return false;
		}
		return true;
	}

	vector<int> getmin(vector<int> a,vector<int> b){
		vector<int> c(a.size());
		for(int i=(int)a.size()-1;i>=0;i--){
			if(a[i]<b[i])return a;
			if(a[i]>b[i])return b;
		}
		return a;
	}

	void bfs(int s){
		memset(level,-1,sizeof(level));
		queue<int> que;
		level[s]=0;
		que.push(s);
		while(que.size()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(!checkemp(e.cap) && level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}
	vector<int> dfs(int v,int t,vector<int> f){
		if(v==t)return f;
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(!checkemp(e.cap) && level[v]<level[e.to]){
				vector<int> d=dfs(e.to,t,getmin(f,e.cap));
				if(!checkemp(d)){
					for(int j=0;j<e.cap.size();j++){
						e.cap[j]-=d[j];
						G[e.to][e.rev].cap[j]+=d[j];
					}
					return d;
				}
			}
		}
		vector<int> zer(f.size(),0);
		return zer;
	}
	vector<int> max_flow(int s,int t,int size){
		vector<int> flow(size,0);
		vector<int> alINF(size,INF);
		while(1){
			bfs(s);
			if(level[t]<0)return flow;
			memset(iter,0,sizeof(iter));
			vector<int> f;
			while(!checkemp(f=dfs(s,t,alINF))){
				for(int i=0;i<size;i++){
					flow[i]+=f[i];
				}
			}
		}
	}
};

string get_string(int v){
	string ret="";
	while(v>0){
		ret+=('0'+v%10);
		v/=10;
	}
	reverse(ret.begin(),ret.end());
	return ret;
}


dinic di;

int n,m;


int main(void){
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)break;
		for(int i=0;i<n;i++){
			di.G[i].clear();
		}
		for(int i=0;i<m;i++){
			int u,v;
			string str;
			cin >> u >> v >> str;
			u--;
			v--;
			int digit=0;
			vector<int> tp(51,0);
			for(int j=0;j<str.size();j++){
				if(str[j]>='0' && str[j]<='9'){
					digit*=10;
					digit+=(str[j]-'0');
				}else if(str[j]=='x'){
					if(digit==0)digit=1;
					if(j+1<str.size() && str[j+1]=='^'){
						j++;
						j++;
						int dg2=0;
						while((str[j]>='0' && str[j]<='9')){
							dg2*=10;
							dg2+=(str[j]-'0');
							j++;
						}
						tp[dg2]=digit;
					}else{
						tp[1]=digit;
					}
					digit=0;
				}
			}
			if(digit>0){
				tp[0]=digit;
			}
			di.add_edge(u,v,tp);
			
		}
		vector<int> ans=di.max_flow(0,n-1,51);
		string best="";
		bool flag=false;
		for(int i=50;i>=0;i--){
			if(ans[i]>0){
				if(flag)best+='+';
				best+=get_string(ans[i]);
				if(i>0){
					if(ans[i]==1){
						best.erase(best.end()-1);
					}
					best+="x";
					if(i>1){
						best+="^";
						best+=get_string(i);
					}
					
				}
				flag=true;
			}
		}
		if(best.size()==0)best+='0';
		cout << best << endl;
	}
	return 0;
}