#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct edge{
	int to,rev;
	vector<int> cap;
	edge(){}
	edge(int tt,vector<int> cc,int rr){
		to=tt;
		rev=rr;
		cap.resize(cc.size());
		for(int i=0;i<cc.size();i++){
			cap[i]=cc[i];
		}
	}
};

class dinic{
public:
	const int INF=100000;
	vector<edge> G[501];
	int level[501];
	int iter[501];
	void add_edge(int from,int to,vector<int> cap){
		G[from].push_back(edge(to,cap,G[to].size()));
		G[to].push_back(edge(from,cap,G[from].size()-1));
	}

	bool checkemp(vector<int> &cap){
		int s=cap.size();
		for(int i=s-1;i>=0;i--){
			if(cap[i]>0)return false;
		}
		return true;
	}

	vector<int> getmin(vector<int> a,vector<int> b){
		vector<int> c(a.size());
		for(int i=(int)a.size()-1;i>=0;i--){
			if(a[i]<b[i])return a;
			if(a[i]>b[i])return b;
		}
		return a;
	}

	void bfs(int s){
		memset(level,-1,sizeof(level));
		queue<int> que;
		level[s]=0;
		que.push(s);
		while(que.size()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(!checkemp(e.cap) && level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}
	vector<int> dfs(int v,int t,vector<int> f){
		if(v==t)return f;
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(!checkemp(e.cap) && level[v]<level[e.to]){
				vector<int> d=dfs(e.to,t,getmin(f,e.cap));
				if(!checkemp(d)){
					for(int j=0;j<e.cap.size();j++){
						e.cap[j]-=d[j];
						G[e.to][e.rev].cap[j]+=d[j];
					}
					return d;
				}
			}
		}
		vector<int> zer(f.size(),0);
		return zer;
	}
	vector<int> max_flow(int s,int t,int size){
		vector<int> flow(size,0);
		vector<int> alINF(size,INF);
		while(1){
			bfs(s);
			if(level[t]<0)return flow;
			memset(iter,0,sizeof(iter));
			vector<int> f;
			while(!checkemp(f=dfs(s,t,alINF))){
				for(int i=0;i<size;i++){
					flow[i]+=f[i];
				}
			}
		}
	}
};

string get_string(int v){
	string ret="";
	while(v>0){
		ret+=('0'+v%10);
		v/=10;
	}
	reverse(ret.begin(),ret.end());
	return ret;
}


dinic di;

int n,m;


int main(void){
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)break;
		for(int i=0;i<n;i++){
			di.G[i].clear();
		}
		for(int i=0;i<m;i++){
			int u,v;
			string str;
			cin >> u >> v >> str;
			u--;
			v--;
			int digit=0;
			vector<int> tp(51,0);
			for(int j=0;j<str.size();j++){
				if(str[j]>='0' && str[j]<='9'){
					digit*=10;
					digit+=(str[j]-'0');
				}else if(str[j]=='x'){
					if(digit==0)digit=1;
					if(j+1<str.size() && str[j+1]=='^'){
						j++;
						j++;
						int dg2=0;
						while((str[j]>='0' && str[j]<='9')){
							dg2*=10;
							dg2+=(str[j]-'0');
							j++;
						}
						tp[dg2]=digit;
					}else{
						tp[1]=digit;
					}
					digit=0;
				}
			}
			if(digit>0){
				tp[0]=digit;
			}
			di.add_edge(u,v,tp);
			
		}
		vector<int> ans=di.max_flow(0,n-1,51);
		string best="";
		bool flag=false;
		for(int i=50;i>=0;i--){
			if(ans[i]>0){
				if(flag)best+='+';
				best+=get_string(ans[i]);
				if(i>0){
					if(ans[i]==1){
						best.erase(best.end()-1);
					}
					best+="x";
					if(i>1){
						best+="^";
						best+=get_string(i);
					}
					
				}
				flag=true;
			}
		}
		if(best.size()==0)best+='0';
		cout << best << endl;
	}
	return 0;
}

Measured memory_bytes: 3440