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 <stdlib.h>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

string toStr(long long n)
{
	char buf[50];
	sprintf(buf, "%d", n);
	return buf;
}

struct poly{
	long long a[55];
	poly(){
		for(long long i = 0; i <= 51; i++) a[i] = 0;
	}
	poly(string s)
	{
		for(long long i = 0; i <= 51; i++) a[i] = 0;
		
		s = s + "+";
		string buf;
		long long state = 0, coe;
		for(long long i = 0; i < s.size(); i++){
			if(state == 0){
				if(s[i] == 'x'){
					if(buf == "") buf = "1";
					coe = atoi(buf.c_str());
					buf = "";
					state = 1;
				}
				else if(s[i] == '+'){
					a[0] = atoi(buf.c_str());
					buf = "";
				}
				else{
					buf += s[i];
				}
			}
			else if(state == 1){
				if(s[i] == '^'){
					state = 2;
				}
				else if(s[i] == '+'){
					a[1] = coe;
					state = 0;
				}
			}
			else if(state == 2){
				if(s[i] == '+'){
					a[atoi(buf.c_str())] = coe;
					buf = "";
					state = 0;
				}
				else{
					buf += s[i];
				}
			}
		}
	}
	string output()
	{
		string ret;
		for(long long i = 51; i > 0; i--){
			if(a[i] == 0) continue;
			if(a[i] != 1) ret += toStr(a[i]);
			ret += "x";
			if(i > 1) ret += "^" + toStr(i);
			ret += "+";
		}
		if(ret.size() > 0){
			if(a[0] == 0) ret.erase(ret.end()-1);
			else ret += toStr(a[0]);
		}
		else ret = toStr(a[0]);
		return ret;
	}
	poly operator+(const poly& obj)
	{
		poly ret;
		for(long long i = 0; i <= 51; i++){
			ret.a[i] = a[i] + obj.a[i];
		}
		return ret;
	}
	poly operator-(const poly& obj)
	{
		poly ret;
		for(long long i = 0; i <= 51; i++){
			ret.a[i] = a[i] - obj.a[i];
		}
		return ret;
	}
	bool operator<(const poly& obj)const
	{
		for(long long i = 51; i >= 0; i--){
			if(a[i] < obj.a[i]) return true;
			if(a[i] > obj.a[i]) return false;
		}
		return false;
	}
	bool operator<=(const poly& obj)const
	{
		for(long long i = 51; i >= 0; i--){
			if(a[i] < obj.a[i]) return true;
			if(a[i] > obj.a[i]) return false;
		}
		return true;
	}
};


struct edge{
	long long to, rev;
	poly cap;
	edge(long long a, string b, long long c){
		to = a, cap = b, rev = c;
	}
};

long long N, M;
vector<edge> G[205];
long long S, T;
bool used[205];
const poly zero, inf("x^51");

poly dfs(long long v, poly f)
{
	used[v] = true;
	if(v == T) return f;
	
	poly ret;
	for(long long i = 0; i < G[v].size(); i++){
		if(used[G[v][i].to] || G[v][i].cap <= zero) continue;
		ret = dfs(G[v][i].to, min(f, G[v][i].cap));
		if(zero < ret){
			G[v][i].cap = G[v][i].cap - ret;
			G[G[v][i].to][G[v][i].rev].cap = G[G[v][i].to][G[v][i].rev].cap + ret;
			return ret;
		}
	}
	return zero;
}

int main(void)
{
	while(1){
		cin >> N >> M;
		if(N == 0 && M == 0) break;
		
		for(long long i = 1; i <= N; i++) G[i].clear();
		
		long long u, v; string s;
		for(long long i = 0; i < M; i++){
			cin >> u >> v >> s;
			G[u].push_back(edge(v, s, G[v].size()));
			G[v].push_back(edge(u, "0", G[u].size()-1));
			G[v].push_back(edge(u, s, G[u].size()));
			G[u].push_back(edge(v, "0", G[v].size()-1));
		}
		S = 1, T = N;
		
		poly ans, flow;
		while(1){
			for(long long i = 1; i <= T; i++) used[i] = false;
			flow = dfs(S, inf);
			if(flow <= zero) break;
			ans = ans + flow;
		}
		
		cout << ans.output() << endl;
	}
	
	return 0;
}
