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>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
//const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

typedef vi Poly;

const Poly ZERO(51, 0);
const Poly INF(51, 1e8);

Poly operator-(const Poly& a, const Poly b)
{
	Poly res(51);
	REP(i, 51) res[i] = a[i] - b[i];
	return res;
}

Poly operator+(const Poly& a, const Poly b)
{
	Poly res(51);
	REP(i, 51) res[i] = a[i] + b[i];
	return res;
}

bool operator<(const Poly& a, const Poly& b)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == b[i]) continue;
		return a[i] < b[i];
	}
	return false;
}

bool operator<=(const Poly& a, const Poly& b)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == b[i]) continue;
		return a[i] < b[i];
	}
	return true;
}

bool operator>(const Poly& a, const Poly& b)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == b[i]) continue;
		return a[i] > b[i];
	}
	return false;
}

Poly min(const Poly& a, const Poly& b)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == b[i]) continue;
		if (a[i] < b[i]) return a;
		else return b;
	}
	return b;
}

bool resid(const Poly& a)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == 0) continue;
		return a[i] > 0;
	}
	return false;
}

template <typename Flow>
struct FEdge {
	int from, to;
	Flow cap; int rev;
	FEdge(int s, int t, Flow f, int r) : from(s), to(t), cap(f), rev(r) {}
};

template<typename Flow> using FGraph = vector<vector<FEdge<Flow>>>;

template <typename Flow>
void add_edge(FGraph<Flow> &g, int from, int to, Flow cap) {
	g[from].emplace_back(from, to, cap, (int)g[to].size());
	g[to].emplace_back(to, from, ZERO, (int)g[from].size() - 1);
}

template <typename Flow>
Flow augment(FGraph<Flow> &g, vi &d, vector<int> &iter, int v, int t, const Flow &f) 
{
	if (v == t || !resid(f)) return f;
	for (int &i = iter[v]; i < (int)g[v].size(); i++) {
		auto &e = g[v][i];
		if (e.cap > ZERO && d[v] < d[e.to]) {
			Flow ff = augment(g, d, iter, e.to, t, min(f, e.cap));
			if (resid(ff)) {
				e.cap = e.cap - ff;
				g[e.to][e.rev].cap = g[e.to][e.rev].cap + ff;
				return ff;
			}
		}
	}
	return ZERO;
}

template <typename Flow>
Flow max_flow(FGraph<Flow> &g, int s, int t, Flow zero = ZERO) {
	int V = g.size();
	Flow flow = zero;
	for (;;) {
		vi d(V, -1);
		queue<int> que;
		d[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (const auto &e : g[v]) {
				if (e.cap <= zero ||  d[e.to] >= 0) continue;
				d[e.to] = d[v] + 1;
				que.push(e.to);
			}
		}
		if (d[t] < 0) return flow;
		vector<int> iter(V, 0);
		Flow f;
		while ((f = augment(g, d, iter, s, t, INF)) > ZERO) flow = flow + f;
	}
}


int num(const string& s, int& p)
{
	assert(isdigit(s[p]));
	int res = 0;
	while (isdigit(s[p]))
	{
		res *= 10;
		res += s[p] - '0';
		p++;
	}
	return res;
}

Poly parse(const string& s)
{
	Poly res(51);
	int n = s.size();
	int p = 0;
	while (p < n)
	{
		int c = 1;
		if (isdigit(s[p]))
		{
			c = num(s, p);
		}
		if (s[p] == 'x')
		{
			p++;
			if (s[p] == '^')
			{
				p++;
				int m = num(s, p);
				res[m] = c;
				p++;
				continue;
			}
			else
			{
				res[1] = c;
				p++;
				continue;
			}
		}
		else
		{
			assert(p == n);
			res[0] = c;
		}
	}
	return res;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, m;
	while (cin >> n >> m, n)
	{
		FGraph<Poly> g(n);
		REP(i, m)
		{
			int a, b; cin >> a >> b; a--; b--;
			string s; cin >> s;
			Poly t = parse(s);
			add_edge(g, a, b, t);
			add_edge(g, b, a, t);
		}
		Poly ans = max_flow(g, 0, n - 1);
		string anss;
		for (int i = 50; i >= 0; i--)
		{
			if (ans[i] > 0)
			{
				if (i > 1)
				{
					if (ans[i] > 1)
					{
						anss += to_string(ans[i]) + "x^" + to_string(i) + "+";
					}
					else
					{
						anss += "x^" + to_string(i) + "+";
					}
				}
				else if (i == 1)
				{
					if (ans[i] > 1)
					{
						anss += to_string(ans[i]) + "x+";
					}
					else
					{
						anss += "x+";
					}
				}
				else if (i == 0)
				{
					anss += to_string(ans[i]) + "+";
				}
			}
		}
		if (anss.size() > 0)
		{
			anss.pop_back();
			cout << anss << endl;
		}
		else cout << 0 << endl;
	}
	return 0;
}