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 <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <map>
#include <sstream>
using namespace std;

using Weight = int;
using Capacity = int;
struct Edge {
	int src, dst; Weight weight; Capacity cap;
	Edge(int s, int d, Weight w, Capacity c) : src(s), dst(d), weight(w), cap(c) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

struct FordFulkerson {
	typedef vector<vector<Capacity>> Matrix;
	int n, t;
	vector<bool> vis;
	vector<vector<Capacity>> cap, flow;
	vector<vector<int>> g;
	Capacity inf;
	FordFulkerson(int n)
		: n(n), cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
		g(n, vector<int>()), inf(numeric_limits<Capacity>::max() / 8) {
	}
	FordFulkerson(const Graph &graph) {
		*this = FordFulkerson(graph.size());
		for(int i = 0; i < n; i++) {
			for(auto &e : graph[i]) addEdge(e.src, e.dst, e.cap);
		}
	}
	void addEdge(int u, int v, Capacity c) {
		cap[u][v] += c; cap[v][u] += c; flow[v][u] += c;
		g[u].push_back(v); g[v].push_back(u);
	}
	Capacity solve(int s, int t) {
		this->t = t;
		Capacity res = 0, aug = 1;
		while(aug > 0) {
			vis.assign(n, false);
			res += (aug = augment(s, inf));
		}
		return res;
	}
	Capacity augment(const int &v, const Capacity &lim) {
		vis[v] = true;
		if(v == t) return lim;
		for(const int &d : g[v]) {
			if(vis[d] || flow[v][d] == cap[v][d]) continue;
			Capacity aug = augment(d, min(lim, cap[v][d] - flow[v][d]));
			flow[v][d] += aug;
			flow[d][v] -= aug;
			if(aug > 0) return aug;
		}
		return 0;
	}
};

typedef pair<int, int> Pii;

vector<int> f(string s) {
	replace(s.begin(), s.end(), '+', ' ');
	//cout << s << endl;
	vector<int> ret(51);

	stringstream ss(s);
	while(ss >> s) {
		stringstream ss2(s);
		if(s.find('x') == string::npos) {
			ss2 >> ret[0];
		}
		else {
			char c;
			int a = 1, L = 1;
			if(s[0] != 'x') ss2 >> a;
			if(s.find('^') != string::npos) {
				ss2 >> c >> c >> L; // x^L
			}
			ret[L] = a;
		}
	}
	return ret;
}

int u[500];
int v[500];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	while(cin >> N >> M, N) {
		map<Pii, vector<int> > poly;
		for(int i = 0; i < M; i++) {
			string p;
			cin >> u[i] >> v[i] >> p;
			u[i]--, v[i]--;
			poly[Pii(u[i], v[i])] = f(p);
		}

		vector<int> ans(51);
		for(int i = 50; i >= 0; i--) {
			Graph G(N);

			for(auto&& p : poly) {
				int a = p.first.first, b = p.first.second, c = p.second[i];
				G[a].emplace_back(a, b, 0, c);
				G[b].emplace_back(b, a, 0, c);
			}

			FordFulkerson ff(G);
			int f = ff.solve(0, N - 1);
			ans[i] = f;

			for(int j = 0; j < M; j++) {
				int a = u[j], b = v[j];
				if(ff.flow[a][b] != 0 && ff.flow[a][b] != ff.cap[a][b]) {
					for(int l = 0; l <= i; l++) {
						poly[Pii(a, b)][l] = 1e8;
					}
				}
			}
		}

		bool flag = false;
		for(int i = 50; i >= 0; i--) {
			if(ans[i] == 0) continue;
			if(flag) cout << "+";
			flag = true;
			if(i == 0 || ans[i] != 1) cout << ans[i];
			if(i != 0) cout << "x";
			if(i >= 2) cout << "^" << i;
		}
		if(!flag) cout << 0;
		cout << "\n";
	}
}