#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

struct Polynomial{
  using P = Polynomial;
  vector<Int> co;
  Polynomial():co(1,1){}
  Polynomial(Int s):co(s,0){}
  Polynomial(vector<Int> co):co(co){}
  
  size_t size() const{
    return co.size();
  };

  void shrink(){
    while(co.size()>1u&&!co.back())
      co.pop_back();
  }

  void reduce(){
    Int g=abs(co.back());
    if(!g) return;
    for(Int c:co)
      if(c!=0) g=__gcd(g,abs(c));
    if(co.back()<0) g*=-1;
    for(Int &c:co) c/=g;
  }

  void print(){
    shrink();
    // reduce();    
    Int n=size(),flg=0;    
    if(n==1){      
      cout<<co[0]<<endl;
      return;
    }
    for(Int i=n-1;i>0;i--){
      if(!co[i]) continue;
      flg=1;
      if(i!=n-1&&co[i]>0) cout<<"+";
      if(co[i]==-1) cout<<"-";
      else if(co[i]!=1) cout<<co[i];
      
      cout<<"x";
      if(i!=1) cout<<"^"<<i;
    }
    if(co[0]){
      if(flg&&co[0]>0) cout<<"+";
      cout<<co[0];
    }
    cout<<endl;
  }

  Int operator[](Int i) const{
    return co[i];
  }

  Int &operator[](Int i){
    return co[i];
  }

  P operator-() const{
    P res=*this;
    for(Int &c:res.co) c*=-1;
    return res;
  }

  P operator+(const P &a) const{
    Int n=size(),m=a.size();
    P res(max(n,m));
    for(Int i=0;i<n;i++) res[i]+=co[i];
    for(Int i=0;i<m;i++) res[i]+=a[i];
    return res;
  }
  P operator-(const P &a) const{return *this+(-a);};

  P operator*(const P &a) const{
    Int n=size(),m=a.size();
    P res(n+m);
    for(Int i=0;i<n;i++)
      for(Int j=0;j<m;j++)
        res[i+j]+=co[i]*a[j];
    res.shrink();
    return res;
  }

  P pow(Int k) const{
    P a(*this);
    P res;
    for(Int i=0;i<k;i++) res=res*a;
    return res;
  }
  
  pair<P, P> divide(const P &a) const{
    Int n=size(),m=a.size(),s=n-m+1;
    if(s<0) return make_pair(P(1),*this);
    P div(s);
    P rest=*this;
    for(Int i=0;i<s;i++){
      if(rest[n-(i+1)]%a[m-1]!=0)
        for(Int &c:rest.co) c*=a[m-1];
      Int d=rest[n-(i+1)]/a[m-1];
      div[s-(i+1)]=d;
      for(Int j=m;j>0;j--) rest[n-(i+j)]-=a[m-j]*d;
    }
    return make_pair(div,rest);
  }
  
  P operator/(const P &a) const{return divide(a).first;};
  P operator%(const P &a) const{return divide(a).second;};  
};

Polynomial gcd(Polynomial a,Polynomial b){
  a.shrink();a.reduce();
  b.shrink();b.reduce();
  if(a.size()<b.size()) swap(a,b);
  if(b.size()==1u&&!b[0]) return a;
  return gcd(b,a%b);
}

Polynomial expr(string s,Int &p);
Polynomial factor(string s,Int &p);
Polynomial term(string s,Int &p);
Int number(string s,Int &p);

Polynomial expr(string s,Int &p){
  //cout<<"expr"<<endl;
  Polynomial res;
  if(s[p]=='-'){
    p++;
    res=-factor(s,p);
  }else res=factor(s,p);
  
  while(p<(Int)s.size()){
    //res.print();
    if(s[p]=='+'){
      p++;
      res=res+factor(s,p);
      continue;
    }
    if(s[p]=='-'){
      p++;
      res=res-factor(s,p);
      continue;
    }
    break;
  }
  //res.print();
  return res;
}
Polynomial factor(string s,Int &p){
  //cout<<"factor"<<endl;
  Polynomial res=term(s,p);
  while(p<(Int)s.size()){
    //res.print();
    if(s[p]=='+') break;
    if(s[p]=='-') break;
    if(s[p]==')') break;
    res=res*term(s,p);
  }
  return res;
}
Polynomial term(string s,Int &p){
  //cout<<"term"<<endl;
  if(s[p]=='('){
    p++;
    Polynomial res=expr(s,p);
    assert(s[p]==')');
    p++;
    if(s[p]=='^'){
      p++;
      Int k=number(s,p);
      res=res.pow(k);
    }
    //res.print();
    return res;
  }
  Int v=(s[p]=='x'?1:number(s,p));
  if(p<(Int)s.size()&&s[p]=='x'){      
    p++;
    if(p<(Int)s.size()&&s[p]=='^'){
      p++;
      Int k=number(s,p);
      Polynomial res(k+1);
      res[k]=v;
      //res.print();
      return res;
    }
    Polynomial res(2);
    res[1]=v;
    //res.print();
    return res;
  }
  Polynomial res(1);
  res[0]=v;
  return res;
}

Int number(string s,Int &p){
  Int res=0;
  while(p<(Int)s.size()&&isdigit(s[p]))
    res=res*10+(s[p++]-'0');
  return res;
}

Polynomial calc(string s){
  Int p=0;
  return expr(s,p);
}


template<typename T,bool directed>
struct Dinic{
  struct edge {
    Int to;
    T cap;
    Int rev;
    edge(){}
    edge(Int to,T cap,Int rev):to(to),cap(cap),rev(rev){}
  };

  T INF;
  vector<vector<edge> > G;
  vector<Int> level,iter;

  Dinic(){}  
  Dinic(Int n,T INF):INF(INF),G(n),level(n),iter(n){}
  
  void add_edge(Int from,Int to,Int cap){
    G[from].emplace_back(to,cap,G[to].size());
    G[to].emplace_back(from,directed?0:cap,G[from].size()-1);
  }
  
  void bfs(Int s){
    fill(level.begin(),level.end(),-1);
    queue<Int> que;
    level[s]=0;
    que.emplace(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.emplace(e.to);
        }
      }
    }
  }
  
  T dfs(Int v,Int t,T 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]){
        T d=dfs(e.to,t,min(f,e.cap));
        if(d==0) continue;
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;      
      }
    }
    return 0;
  }
  
  T flow(Int s,Int t,T lim){
    T fl=0;
    while(1){
      bfs(s);
      if(level[t]<0||lim==0) break;
      fill(iter.begin(),iter.end(),0);
      
      while(1){
        T f=dfs(s,t,lim);
        if(f==0) break;
        fl+=f;
        lim-=f;
      }
    }
    return fl;
  }

  T flow(Int s,Int t){
    return flow(s,t,INF);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  while(cin>>n>>m,n){
    using P = pair<Int, Polynomial>;
    vector<vector<P> > G(n);
    for(Int i=0;i<m;i++){
      Int x,y;
      string s;
      cin>>x>>y>>s;
      auto p=calc(s);
      x--;y--;
      G[x].emplace_back(y,p);
      G[y].emplace_back(x,p);
    }
    const Int INF = 1e5;
    Dinic<Int, true> F(n,INF);
    Polynomial ans(1);
    
    for(Int d=50;d>=0;d--){   
      for(Int v=0;v<n;v++){
        for(auto e:G[v]){
          Int u=e.first;
          auto &p=e.second;
          if(d<(Int)p.size()&&p[d]){
            F.add_edge(v,u,p[d]);
          }          
        }
      }
      Polynomial res(d+1);
      res[d]=F.flow(0,n-1);
      ans=ans+res;
      
      for(auto &v:F.G)
        for(auto &e:v)
          if(e.cap>0) e.cap=INF;
    }
    ans.print();
  } 
  return 0;
}



Measured memory_bytes: 6736