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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt" > "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\b.answer"



#define _GLIBCXX_DEBUG

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()


const long long int L_INF = 9223372036854775807;

typedef vector<int> Weight;
const Weight INF = vector<int>(100, 1);
const Weight ZERO = vector<int>(100, 0);
struct Edge {
	int src, dst;
	Weight weight;
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
};
bool operator <(const Weight&l, const Weight&r) {
	for (int i = 99; i >=0; --i) {
		if (l[i] != r[i])return l[i] < r[i];
	}
	return false;
}
bool operator >(const Weight&l, const Weight&r) {
	for (int i = 99; i >= 0; --i) {
		if (l[i] != r[i])return l[i] > r[i];
	}
	return false;
}
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
Weight operator+(const Weight&l, const Weight&r) {
	vector<int>ans(100);
	for (int i = 0; i < 100; ++i) {
		ans[i] = l[i] + r[i];
	}
	return ans;
}
Weight operator-(const Weight&l, const Weight&r) {
	vector<int>ans(100);
	for (int i = 0; i < 100; ++i) {
		ans[i] = l[i] - r[i];
	}
	return ans;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;
#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])

//??????0??????????????????????????¨??£???????±??????????????????§??¨???
Weight maximumFlow(const Graph &ag, int s, int t) {

	Graph g(ag);
	for (int i = 0; i < ag.size(); ++i) {
		for (int j = 0; j < ag[i].size(); ++j) {
			int d = ag[i][j].dst;
			int s = ag[i][j].src;

			bool ok = false;
			for (int k = 0; k < ag[d].size(); ++k) {
				if (ag[d][k].src == s) {
					ok = true;
					break;
				}
			}
			if (!ok) {
				g[d].push_back(Edge(d, s, ag[i][j].weight));
			}
		}
	}
	int n = g.size();
	Matrix flow(n, Array(n,ZERO)), capacity(n, Array(n, ZERO));
	REP(u, n) FOR(e, g[u]) capacity[e->src][e->dst] =capacity[e->src][e->dst]+ e->weight;


	Weight total = ZERO;
	while (1) {
		queue<int> Q; Q.push(s);
		vector<int> prev(n, -1); prev[s] = s;
		while (!Q.empty() && prev[t] < 0) {
			int u = Q.front(); Q.pop();
			FOR(e, g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > ZERO) {
				prev[e->dst] = u;
				Q.push(e->dst);
			}
		}
		if (prev[t] < 0)break; // prev[x] == -1 <=> t-side
		Weight inc = INF;
		for (int j = t; prev[j] != j; j = prev[j]) {
			auto v(RESIDUE(prev[j], j));
			if (inc > v) {
				inc =v;
			}
		}
		for (int j = t; prev[j] != j; j = prev[j])
			flow[prev[j]][j] =flow[prev[j]][j]+inc, flow[j][prev[j]] =flow[j][prev[j]]- inc;
		total =total+ inc;
	}

	return total;
}
int a = 0;
string st;
int getnum() {
	int num = 0;
	while (a!=st.size()&&isdigit(st[a])) {
		num = num * 10 + st[a] - '0';
		a++;
	}
	return num;
}
pair<int, int>getx() {
	int num = 1;
	if (isdigit(st[a])) {
		num = getnum();
	}
	int base;
	if (a == st.size() || st[a] == '+') {
		base = 0;
	}
	else {
		assert(st[a] == 'x');
		a++;
		if (a == st.size() || st[a] == '+') {
			base = 1;
		}
		else {
			assert(st[a] == '^');
			a++;
			base = getnum();
		}
	}
	return make_pair(base, num);
}
vector<int>getvec() {
	vector<int>v(100);
	auto p = getx();
	v[p.first] = p.second;
	while (a != st.size()) {
		a++;
		auto p = getx();
		v[p.first] = p.second;
	}
	return v;
}
void makest(const vector<int>&vs) {

	bool fst = true;
	for (int i = 99; i >= 0; --i) {
		if (vs[i]) {
			if (!fst)cout << "+";
			if (i) {
				if (vs[i] >= 2) {
					cout << vs[i];
				}
				if (i >= 1) {
					cout << 'x';
					if (i >= 2) {
						cout << '^';
						cout << i;
					}
				}
			}
			else {
				cout << vs[i];
			}
			
			fst =false;
		}
	}
	if (fst)cout << '0';
	cout << endl;
}

int main() {
	while (1) {
		int N, M; cin >> N >> M;
		if (!N)break;
		Graph g(N);
		for (int i = 0; i < M; ++i) {
			int u, v; string p; cin >> u >> v >> p;
			st = p;
			u--; v--;
			a = 0;
			auto aa(getvec());
			g[u].emplace_back(u, v, aa);
		}
		Weight ans = maximumFlow(g, 0, N - 1);
		makest(ans);
	}
	
	return 0;
}