#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

string toStr(long long n)
{
	char buf[50];
	sprintf(buf, "%d", n);
	return buf;
}

struct poly{
	long long a[55];
	poly(){
		for(long long i = 0; i <= 51; i++) a[i] = 0;
	}
	poly(string s)
	{
		for(long long i = 0; i <= 51; i++) a[i] = 0;
		
		s = s + "+";
		string buf;
		long long state = 0, coe;
		for(long long i = 0; i < s.size(); i++){
			if(state == 0){
				if(s[i] == 'x'){
					if(buf == "") buf = "1";
					coe = atoi(buf.c_str());
					buf = "";
					state = 1;
				}
				else if(s[i] == '+'){
					a[0] = atoi(buf.c_str());
					buf = "";
				}
				else{
					buf += s[i];
				}
			}
			else if(state == 1){
				if(s[i] == '^'){
					state = 2;
				}
				else if(s[i] == '+'){
					a[1] = coe;
					state = 0;
				}
			}
			else if(state == 2){
				if(s[i] == '+'){
					a[atoi(buf.c_str())] = coe;
					buf = "";
					state = 0;
				}
				else{
					buf += s[i];
				}
			}
		}
	}
	string output()
	{
		string ret;
		for(long long i = 51; i > 0; i--){
			if(a[i] == 0) continue;
			if(a[i] != 1) ret += toStr(a[i]);
			ret += "x";
			if(i > 1) ret += "^" + toStr(i);
			ret += "+";
		}
		if(ret.size() > 0){
			if(a[0] == 0) ret.erase(ret.end()-1);
			else ret += toStr(a[0]);
		}
		else ret = toStr(a[0]);
		return ret;
	}
	poly operator+(const poly& obj)
	{
		poly ret;
		for(long long i = 0; i <= 51; i++){
			ret.a[i] = a[i] + obj.a[i];
		}
		return ret;
	}
	poly operator-(const poly& obj)
	{
		poly ret;
		for(long long i = 0; i <= 51; i++){
			ret.a[i] = a[i] - obj.a[i];
		}
		return ret;
	}
	bool operator<(const poly& obj)const
	{
		for(long long i = 51; i >= 0; i--){
			if(a[i] < obj.a[i]) return true;
			if(a[i] > obj.a[i]) return false;
		}
		return false;
	}
	bool operator<=(const poly& obj)const
	{
		for(long long i = 51; i >= 0; i--){
			if(a[i] < obj.a[i]) return true;
			if(a[i] > obj.a[i]) return false;
		}
		return true;
	}
};


struct edge{
	long long to, rev;
	poly cap;
	edge(long long a, string b, long long c){
		to = a, cap = b, rev = c;
	}
};

long long N, M;
vector<edge> G[205];
long long S, T;
bool used[205];
const poly zero, inf("x^51");

poly dfs(long long v, poly f)
{
	used[v] = true;
	if(v == T) return f;
	
	poly ret;
	for(long long i = 0; i < G[v].size(); i++){
		if(used[G[v][i].to] || G[v][i].cap <= zero) continue;
		ret = dfs(G[v][i].to, min(f, G[v][i].cap));
		if(zero < ret){
			G[v][i].cap = G[v][i].cap - ret;
			G[G[v][i].to][G[v][i].rev].cap = G[G[v][i].to][G[v][i].rev].cap + ret;
			return ret;
		}
	}
	return zero;
}

int main(void)
{
	while(1){
		cin >> N >> M;
		if(N == 0 && M == 0) break;
		
		for(long long i = 1; i <= N; i++) G[i].clear();
		
		long long u, v; string s;
		for(long long i = 0; i < M; i++){
			cin >> u >> v >> s;
			G[u].push_back(edge(v, s, G[v].size()));
			G[v].push_back(edge(u, "0", G[u].size()-1));
			G[v].push_back(edge(u, s, G[u].size()));
			G[u].push_back(edge(v, "0", G[v].size()-1));
		}
		S = 1, T = N;
		
		poly ans, flow;
		while(1){
			for(long long i = 1; i <= T; i++) used[i] = false;
			flow = dfs(S, inf);
			if(flow <= zero) break;
			ans = ans + flow;
		}
		
		cout << ans.output() << endl;
	}
	
	return 0;
}


Measured memory_bytes: 4608