The trafic on the Internet is increasing these days due to smartphones. The wireless carriers have to enhance their network infrastructure.

The network of a wireless carrier consists of a number of base stations and lines. Each line connects two base stations bi-directionally. The bandwidth of a line increases every year and is given by a polynomial f(x) of the year x.

Your task is, given the network structure, to write a program to calculate the maximal bandwidth between the 1-st and N-th base stations as a polynomial of x.



Input

The input consists of multiple datasets. Each dataset has the following format:

N M
u1 v1 p1
...
uM vM pM


The first line of each dataset contains two integers N (2 ≤ N ≤ 50) and M (0 ≤ M ≤ 500), which indicates the number of base stations and lines respectively. The following M lines describe the network structure. The i-th of them corresponds to the i-th network line and contains two integers ui and vi and a polynomial pi. ui and vi indicate the indices of base stations (1 ≤ ui, vi ≤ N); pi indicates the network bandwidth.

Each polynomial has the form of:

aLxL + aL-1xL-1 + ... + a2x2 + a1x + a0

where L (0 ≤ L ≤ 50) is the degree and ai's (0 ≤ i ≤ L, 0 ≤ ai ≤ 100) are the coefficients. In the input,

* each term aixi (for i ≥ 2) is represented as <ai>x^<i>
* the linear term (a1x) is represented as <a1>x;
* the constant (a0) is represented just by digits;
* these terms are given in the strictly decreasing order of the degrees and connected by a plus sign ("+");
* just like the standard notations, the <ai> is omitted if ai = 1 for non-constant terms;
* similarly, the entire term is omitted if ai = 0 for any terms; and
* the polynomial representations contain no space or characters other than digits, "x", "^", and "+".



For example, 2x2 + 3x + 5 is represented as 2x^2+3x+5; 2x3 + x is represented as 2x^3+x, not 2x^3+0x^2+1x+0 or the like. No polynomial is a constant zero, i.e. the one with all the coefficients being zero.

The end of input is indicated by a line with two zeros. This line is not part of any dataset.

Output

For each dataset, print the maximal bandwidth as a polynomial of x. The polynomial should be represented in the same way as the input format except that a constant zero is possible and should be represented by "0" (without quotes).

Example

Input

3 3
1 2 x+2
2 3 2x+1
3 1 x+1
2 0
3 2
1 2 x
2 3 2
4 3
1 2 x^3+2x^2+3x+4
2 3 x^2+2x+3
3 4 x+2
0 0


Output

2x+3
0
2
x+2
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2328"

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

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
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;
}
//END CUT HERE
#ifndef call_from_test
signed YUKI_932(){
  string s;
  cin>>s;
  auto ss=split(s,',');
  cout<<(ss==vector<string>(ss.size(),"AC")?"Done!":"Failed...")<<endl;
  return 0;
}
/*
  verified 2019/11/30
  https://yukicoder.me/problems/no/932
*/

signed main(){
  YUKI_932();
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#endif
//BEGIN CUT HERE
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){}
  };

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

  Dinic(){}
  Dinic(int n):G(n),level(n),iter(n){}

  int add_edge(int from,int to,T cap){
    G[from].emplace_back(to,cap,G[to].size());
    G[to].emplace_back(from,directed?0:cap,G[from].size()-1);
    return G[to].back().rev;
  }

  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,numeric_limits<T>::max()/2);
  }

  T cut(int s,int t,int x,int a){
    static_assert(directed, "must be directed");
    auto &e=G[x][a];
    int y=e.to;
    T cr=G[y][e.rev].cap;
    if(cr==0) return e.cap=0;
    e.cap=G[y][e.rev].cap=0;
    T cap=cr-flow(x,y,cr);
    if(x!=s&&cap!=0) flow(x,s,cap);
    if(t!=y&&cap!=0) flow(t,y,cap);
    return cap;
  }

  T link(int s,int t,int x,int a,T f){
    auto &e=G[x][a];
    e.cap+=f;
    return flow(s,t,f);
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed SPOJ_FASTFLOW(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int n,m;
  cin>>n>>m;
  Dinic<Int, false> G(n);
  for(Int i=0;i<m;i++){
    Int a,b,c;
    cin>>a>>b>>c;
    if(a==b) continue;
    a--;b--;
    G.add_edge(a,b,c);
  }
  cout<<G.flow(0,n-1)<<endl;
  return 0;
}
/*
  verified on 2019/06/10
  https://www.spoj.com/problems/FASTFLOW/
*/

signed SPOJ_BANKROB(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m,s,t;
  cin>>n>>m>>s>>t;
  s--;t--;
  const int INF=5050;
  Dinic<int, true> G(n*2);
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    G.add_edge(n+x,y,INF);
    G.add_edge(n+y,x,INF);
  }

  for(int i=0;i<n;i++)
    G.add_edge(i,n+i,1);

  cout<<G.flow(n+s,t)<<endl;
  return 0;
}
/*
  verified on 2019/06/10
  https://www.spoj.com/problems/BANKROB/
*/

signed main(){
  //SPOJ_FASTFLOW();
  //SPOJ_BANKROB();
  return 0;
}
#endif

#undef call_from_test

signed main(){
  const int DEG = 55;
  const int INF = 1<<28;
  int n,m;
  while(cin>>n>>m,n){
    Dinic<int, false> 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,'+')){
        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=INF;
          e.cap+=ed[i][e.to][flow.G[e.to][e.rev].to];
        }
      }
      ans[i]=flow.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>0) cout<<"x";
      if(i>1) cout<<"^"<<i;
    }
    cout<<endl;
  }
  return 0;
}

