#include <bits/stdc++.h>
using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

typedef vector<vvi> vvvi;
const int L=50;

vi parse(string s)
{
	replace(all(s),'+',' ');
	istringstream iss(s);
	vi res(L+1);
	for(string t;iss>>t;){
		int c=isdigit(t[0])?0:1,i=0;
		for(;i<t.size() && isdigit(t[i]);i++)
			c=c*10+t[i]-'0';
		if(i==t.size()){ // c*x^0
			res[0]+=c;
			continue;
		}
		assert(t[i]=='x');
		i++;
		if(i==t.size()){ // c*x^1
			res[1]+=c;
			continue;
		}
		assert(t[i]=='^');
		i++;
		int r=0;
		for(;i<t.size() && isdigit(t[i]);i++)
			r=r*10+t[i]-'0';
		res[r]+=c;
	}
	return res;
}

struct Edge{
	int src,dst,cap,flow;
	Edge(){}
	Edge(int s,int d,int c,int f=0):src(s),dst(d),cap(c),flow(f){}
};
struct Graph{
	vector<Edge> es;
	vi head,next;
	Graph(){}
	Graph(int n):head(n,-1){}
	// 有向辺を追加するとき逆辺の容量c2は普通0である．
	// 両方向に容量があるならc2も指定する．
	void AddEdge(int u,int v,int c1,int c2=0){
		es.emplace_back(u,v,c1); next.push_back(head[u]); head[u]=es.size()-1;
		es.emplace_back(v,u,c2); next.push_back(head[v]); head[v]=es.size()-1;
	}
};

void BFS(const Graph& g,int tap,vi& layer)
{
	queue<pii> q; q.emplace(tap,0);
	while(q.size()){
		int u,d; tie(u,d)=q.front(); q.pop();
		if(layer[u]!=INF) continue;
		layer[u]=d;
		for(int i=g.head[u];i!=-1;i=g.next[i])
			if(g.es[i].cap-g.es[i].flow>0)
				q.emplace(g.es[i].dst,d+1);
	}
}

int DFS(Graph& g,int v,int sink,const vi& layer,int flow)
{
	if(v==sink) return flow;
	int f=flow;
	for(int& i=g.head[v];i!=-1;i=g.next[i]){
		Edge& e=g.es[i];
		if(layer[e.src]>=layer[e.dst]) continue;
		int residue=e.cap-e.flow;
		if(residue==0) continue;
		int augment=DFS(g,e.dst,sink,layer,min(residue,f));
		e.flow+=augment;
		g.es[i^1].flow-=augment;
		f-=augment;
		if(f==0) break;
	}
	return flow-f;
}

int Dinic(Graph& g,int tap,int sink)
{
	int res=0;
	for(int n=g.head.size();;){
		vi layer(n,INF);
		BFS(g,tap,layer);
		if(layer[sink]==INF) break;
		vi temp=g.head;
		res+=DFS(g,tap,sink,layer,INF);
		swap(g.head,temp);
	}
	return res;
}

int main()
{
	for(int n,m;cin>>n>>m && n|m;){
		vvvi c(n,vvi(n,vi(L+1)));
		rep(i,m){
			int u,v; cin>>u>>v; u--,v--;
			string s; cin>>s;
			vi tmp=parse(s);
			rep(j,L+1){
				c[u][v][j]+=tmp[j];
				c[v][u][j]+=tmp[j];
			}
		}
		
		vi res(L+1);
		per(k,L+1){
			Graph g(n);
			rep(i,n) repi(j,i+1,n) if(c[i][j][k] || c[j][i][k])
				g.AddEdge(i,j,c[i][j][k],c[j][i][k]);
			res[k]=Dinic(g,0,n-1);
			if(k==0) continue;
			for(auto e:g.es)
				if(e.cap-e.flow>0)
					c[e.src][e.dst][k-1]=INF;
		}
		
		bool first=true;
		per(i,res.size()) if(res[i] || (first && i==0)){
			if(!first) cout<<'+';
			else       first=false;
			if(res[i]>1 || i==0) cout<<res[i];
			if(i>0) cout<<'x';
			if(i>1) cout<<'^'<<i;
		}
		cout<<endl;
	}
}

Measured memory_bytes: 1792