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;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

struct Polynomial {
	using Val = int;
	using Coef = int;
	int n; // dimension = degree + 1
	vector<Coef> coefs;
	Polynomial() :n(1), coefs(1) {}
	explicit Polynomial(int n) :n(n), coefs(n) {}
	explicit Polynomial(int n, Coef c) :n(n), coefs(n) { coefs[n - 1] = c; }
	void resize(int n) { this->n = n; coefs.resize(n); }
	void normalize() {
		int i = n;
		while (i > 1 && coefs[i - 1] == Coef())i--;
		resize(i);
	}
	bool operator<(const Polynomial &that)const {
		for (int i = that.n; i > n; i--)
			if (that.coefs[i - 1] > Coef())
				return true;
			else if (that.coefs[i - 1] < Coef())
				return false;
		for (int i = n; i > that.n; i--)
			if (coefs[i - 1] > Coef())
				return false;
			else if (coefs[i - 1] < Coef())
				return true;
		for (int i = min(n, that.n); i > 0; i--)
			if (coefs[i - 1] < that.coefs[i - 1])
				return true;
			else if (coefs[i - 1] > that.coefs[i - 1])
				return false;
		return false;
	}
	bool operator>(const Polynomial &that)const { return that < *this; }
	bool operator<=(const Polynomial &that)const { return !(that < *this); }
	bool operator>=(const Polynomial &that)const { return !(*this < that); }
	bool operator==(const Polynomial &that)const { return !(*this < that) && !(that < *this); }
	bool operator!=(const Polynomial &that)const { return !(*this == that); }
	Polynomial &operator+=(const Polynomial &that) {
		if (n < that.n)
			resize(that.n);
		for (int i = 0; i < that.n; i++)
			coefs[i] += that.coefs[i];
		normalize();
		return *this;
	}
	Polynomial &operator-=(const Polynomial &that) {
		if (n < that.n)
			resize(that.n);
		for (int i = 0; i < that.n; i++)
			coefs[i] -= that.coefs[i];
		normalize();
		return *this;
	}
	Polynomial operator+(const Polynomial &that)const { return Polynomial(*this) += that; }
	Polynomial operator-(const Polynomial &that)const { return Polynomial(*this) -= that; }

	Val evaluate(Val a)const {
		Val ans = 0, x = 1;
		for (int i = 0; i < n; i++) {
			ans += x*coefs[i];
			x *= a;
		}
		return ans;
	}
};

ostream &operator<<(ostream &o, const Polynomial &p) {
	bool first = true;
	for (int i = p.n - 1; i >= 0; i--) {
		Polynomial::Coef c = p.coefs[i];
		if (c != 0) {
			if (first && c < 0)o << "-";
			else if (first)o << "";
			else if (c < 0)o << "-";
			else o << "+";

			if (i != 0 && (c == 1 || c == -1))o << "";
			else if (c < 0)o << -c;
			else o << c;

			if (i == 0)o << "";
			else if (i == 1)o << "x";
			else o << "x^" << i;

			first = false;
		}
	}
	if (first)o << "0";
	return o;
}

const Polynomial kPolynomialInf(55, INF);



struct Dinic {
	using Flow = Polynomial;
	const Flow kInf = kPolynomialInf;
	struct Edge {
		int to, rev;
		Flow cap;
		Edge() {}
		Edge(int to, int rev, Flow cap) :to(to), rev(rev), cap(cap) {}
	};
	int n;
	vector<vector<Edge>> g;
	vector<bool> used;
	vector<int> level;
	vector<int> iter;
	Dinic(int n) :n(n), g(n), used(n), level(n), iter(n) {};
	void addArc(int from, int to, Flow cap) {
		g[from].emplace_back(to, (int)g[to].size(), cap);
		g[to].emplace_back(from, (int)g[from].size() - 1, Flow());
	}
	void addEdge(int a, int b, Flow cap) {
		g[a].emplace_back(b, (int)g[b].size(), cap);
		g[b].emplace_back(a, (int)g[a].size() - 1, cap);
	}
	Flow maximumFlow(int s, int t) {
		Flow total = Flow();
		while (true) {
			levelize(s);
			if (level[t] < 0)return total;
			fill(iter.begin(), iter.end(), 0);
			Flow f;
			while (true) {
				f = augment(s, t, kInf);
				if (f == Flow())break;
				total += f;
			}
		}
	}
	Flow augment(int v, int t, Flow f) {
		if (v == t)return f;
		for (int &i = iter[v]; i < g[v].size(); i++) {
			Edge &e = g[v][i];
			if (e.cap > Flow() && level[v] < level[e.to]) {
				Flow d = augment(e.to, t, min(f, e.cap));
				if (d > Flow()) {
					e.cap -= d;
					g[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return Flow();
	}
	void levelize(int s) {
		fill(level.begin(), level.end(), -1);
		queue<int> q;
		level[s] = 0;
		q.push(s);
		while (q.size()) {
			int v = q.front(); q.pop();
			for (int i = 0; i < g[v].size(); i++) {
				Edge &e = g[v][i];
				if (e.cap > Flow() && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}
};

struct Parser {
	using Iter = string::const_iterator;
	const char kTerminator = '$';
	string s;
	Iter it;
	Parser(const string &t) :s(t) { s += kTerminator; it = s.begin(); }
	void cmp(char expected) { if (*it != expected)cerr << *it << " is not " << expected << endl; assert(*it == expected); }
	Polynomial a() {
		Polynomial ret = b();
		while (true) {
			if (*it == '+') {
				it++;
				ret += b();
			}
			else if (*it == '-') {
				it++;
				ret -= b();
			}
			else break;
		}
		return ret;
	}
	Polynomial b() {
		int coef = integer();
		int degree = 0;
		if (*it == 'x') {
			coef = max(1, coef);
			it++;
			if (*it == '^') {
				it++;
				degree = integer();
			}
			else
				degree = 1;
		}
		return Polynomial(degree + 1, coef);
	}
	int integer() {
		int ret = 0;
		while (isdigit(*it)) {
			ret *= 10;
			ret += *it - '0';
			it++;
		}
		return ret;
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	for (int N, M; cin >> N >> M&&N;) {
		Dinic dinic(N);
		rep(i, 0, M) {
			int u, v; string p;
			cin >> u >> v >> p; u--, v--;
			Parser parser(p);
			Polynomial poly = parser.a();
			dinic.addEdge(u, v, poly);
		}
		cout << dinic.maximumFlow(0, N - 1) << endl;
	}
	return 0;
}