#include<bits/stdc++.h>
using namespace std;
using Int = long long;
vector<string> split(string& s,char c){
  int n=s.size();
  vector<string> res;
  for(int i=0;i<n;i++){
    if(s[i]==c) continue;
    string t;
    while(i<n&&s[i]!=c) t.push_back(s[i++]);
    res.push_back(t);
  }
  return res;
}


struct Dinic{
  const int INF=1<<28;
  
  struct edge {
    int to,cap,rev;
    edge(){}
    edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){}
  };

  vector<vector<edge> > G;
  vector<map<int,int> > M;
  vector<int> level,iter;

  Dinic(){}
  Dinic(int V){init(V);}

  void init(int V){
    for(int i=0;i<(int)G.size();i++) G[i].clear();
    G.clear();
    for(int i=0;i<(int)M.size();i++) M[i].clear();
    M.clear();
    level.clear();
    iter.clear();
    G.resize(V);
    M.resize(V);
    level.resize(V);
    iter.resize(V);
  }
  
  void add_edge(int from,int to,int cap){
    M[from][to]=G[from].size();
    M[to][from]=G[to].size();
    G[from].push_back(edge(to,cap,G[to].size()));
    // undirected
    G[to].push_back(edge(from,cap,G[from].size()-1));
    // directed
    // G[to].push_back(edge(from,0,G[from].size()-1));
  }
  
  void bfs(int s){
    fill(level.begin(),level.end(),-1);
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
      int v=que.front();que.pop();
      for(int i=0;i<(int)G[v].size();i++){
	edge &e = G[v][i];
	if(e.cap>0&&level[e.to]<0){
	  level[e.to]=level[v]+1;
	  que.push(e.to);
	}
      }
    }
  }
  
  int dfs(int v,int t,int f){
    if(v==t) return f;
    for(int &i=iter[v];i<(int)G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[v]<level[e.to]){
	int d = dfs(e.to,t,min(f,e.cap));
	if(d>0){
	  e.cap-=d;
	  G[e.to][e.rev].cap+=d;
	  return d;
	}
      }
    }
    return 0;
  }
  
  int max_flow(int s,int t,int lim){
    int flow=0;
    for(;;){
      bfs(s);
      if(level[t]<0||lim==0) return flow;
      fill(iter.begin(),iter.end(),0);
      int f;
      while((f=dfs(s,t,lim))>0){
	flow+=f;
	lim-=f;
      }
    }
  }

  int max_flow(int s,int t){
    return max_flow(s,t,INF);
  }

  //cap==1 only
  bool back_edge(int s,int t,int from, int to){
    for(int i=0;i<(int)G[from].size();i++) {
      edge& e=G[from][i];
      if(e.to==to) {
	if(e.cap==0&&max_flow(from,to,1)==0) {
	  max_flow(from,s,1);
	  max_flow(t,to,1);
	  return 1;
	}
      }
    }
    return 0;
  }
};

const int DEG=55;
signed main(){
  int n,m;
  while(cin>>n>>m,n){
    Dinic flow(n);
    int ed[DEG][55][55];
    memset(ed,0,sizeof(ed));
    
    for(int i=0;i<m;i++){
      int a,b;
      string s;
      cin>>a>>b>>s;
      a--;b--;
      flow.add_edge(a,b,0);
      for(string t:split(s,'+')){
	//cout<<t<<endl;
	if(!count(t.begin(),t.end(),'x')){
	  ed[0][a][b]+=stoi(t);
	  ed[0][b][a]+=stoi(t);
	}else if(t.back()=='x'){
	  t.pop_back();
	  if(t.empty()) t="1";
	  ed[1][a][b]+=stoi(t);
	  ed[1][b][a]+=stoi(t);
	}else{
	  auto v=split(t,'^');
	  v[0].pop_back();
	  if(v[0].empty()) v[0]="1";
	  ed[stoi(v[1])][a][b]+=stoi(v[0]);
	  ed[stoi(v[1])][b][a]+=stoi(v[0]);
	}
      }
    }
    vector<int> ans(DEG);
    for(int i=DEG-1;i>=0;i--){
      for(auto& v:flow.G){
	for(auto& e:v){
	  if(e.cap) e.cap=flow.INF;
	  e.cap+=ed[i][e.to][flow.G[e.to][e.rev].to];
	}
      }
      ans[i]=flow.max_flow(0,n-1);
    }
    bool f=1;
    for(int i=DEG-1;i>=0;i--){
      if(!ans[i]){
	if(i) continue;
	if(f) cout<<ans[i],f=0;
	continue;
      }
      if(!f) cout<<"+";
      f=0;
      if(!(i&&ans[i]==1)) cout<<ans[i];
      if(i) cout<<"x";
      if(i>1) cout<<"^"<<i;
    }
    assert(!f);
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3916