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 <array>
#include <cctype>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct weight {
	static constexpr int MAX_L = 50;
	typedef array<int, MAX_L + 1> A;

	A coefficients;

	inline static int number(string::const_iterator &it) {
		int res = 0;
		while(isdigit(*it)) {
			res = res * 10 + *it - '0';
			++it;
		}
		return res;
	}

	inline void parse(string::const_iterator &it) {
		const int c = (isdigit(*it) ? number(it) : 1);

		if(*it != 'x') {
			coefficients.back() = c;
			return;
		}

		++it;

		int e = 1;
		if(*it == '^') {
			++it;
			e = number(it);
		}

		coefficients[MAX_L - e] = c;
	}

	weight(const string &s = "0") {
		coefficients.fill(0);

		string::const_iterator it = s.cbegin();
		parse(it);
		while(*it == '+') {
			++it;
			parse(it);
		}
	}

	weight(const A &a):coefficients(a) {}
	weight(const weight &w):coefficients(w.coefficients) {}

	inline bool operator<(const weight &w) const {
		return coefficients < w.coefficients;
	}


	inline weight &operator+=(const weight &w) {
		for(unsigned i = 0; i < coefficients.size(); ++i) {
			coefficients[i] += w.coefficients[i];
		}
		return *this;
	}

	inline weight &operator-=(const weight &w) {
		for(unsigned i = 0; i < coefficients.size(); ++i) {
			coefficients[i] -= w.coefficients[i];
		}
		return *this;
	}

	inline string to_string() const {
		string res;
		for(unsigned i = 0; i < coefficients.size(); ++i) {
			if(coefficients[i] != 0) {
				if(res.size()) res += '+';

				const int e = MAX_L - i;

				if(e == 0 || coefficients[i] > 1) {
					res += std::to_string(coefficients[i]);
				}

				if(e >= 1) {
					res += 'x';
					if(e >= 2) res += "^" + std::to_string(e);
				}
			}
		}
		if(res == "") res = "0";
		return res;
	}
};

struct edge {
	int to;
	weight cap;
	int rev;
	edge(int to_, weight cap_, int rev_):to(to_), cap(cap_), rev(rev_){}
};

const weight INF("1000x^50");
const weight ZERO;

vector<vector<edge> > G;
vector<int> level;
vector<int> iter;

void init(int V) {
	G.assign(V, vector<edge>());
	level.resize(V);
	iter.resize(V);
}

void add_edge(int from, int to, weight cap) {
	G[from].emplace_back(to, cap, G[to].size());
	G[to].emplace_back(from, cap, G[from].size() - 1);
}

void bfs(int s) {
	fill(level.begin(), level.end(), -1);
	queue<int> que;
	level[s] = 0;
	que.push(s);

	while(!que.empty()) {
		const int v = que.front();
		que.pop();

		for(const auto &e : G[v]) {
			if(ZERO < e.cap && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}

weight dfs(int v, int t, weight f) {
	if(v == t) return f;

	for(int &i = iter[v]; i < static_cast<int>(G[v].size()); ++i) {
		edge &e = G[v][i];
		if(ZERO < e.cap && level[v] < level[e.to]) {
			const weight d = dfs(e.to, t, min(f, e.cap));
			if(ZERO < d) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}

	return ZERO;
}

weight max_flow(int s, int t) {
	weight flow = ZERO;

	for(;;) {
		bfs(s);
		if(level[t] < 0) return flow;

		fill(iter.begin(), iter.end(), 0);
		for(weight f; ZERO < (f = dfs(s, t, INF)); flow += f);
	}
}


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

	for(int n, m; cin >> n >> m && n;) {
		init(n);

		for(int i = 0; i < m; ++i) {
			int a, b;
			string p;
			cin >> a >> b >> p;
			add_edge(a - 1, b - 1, weight(p));
		}

		cout << max_flow(0, n - 1).to_string() << endl;
	}

	return EXIT_SUCCESS;
}