#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;
}

Measured memory_bytes: 5648