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
#include<bits/stdc++.h>
using namespace std;
struct edge { int to,cap,rev; };
#define MAX 52
#define INF (1e7)
int n;
vector<int> G[MAX][MAX];
bool used[MAX];
vector<int> g[MAX];
vector<int> min(vector<int> &a,vector<int> &b){
  for(int i=MAX-1;i>=0;i--){
    if( a[i]==b[i] )continue;
    if(a[i]>b[i])return b;
    if(a[i]<b[i])return a;
  }
  return a;
}
 
void add(vector<int> &a,vector<int> &b){
  for(int i=0;i<MAX;i++)
    a[i]+=b[i];
}
 
void sub(vector<int> &a,vector<int> b){
  for(int i=0;i<MAX;i++)
    a[i]-=b[i];
}
 
bool check(vector<int> &a){
  for(int i=0;i<MAX;i++)
    if(a[i]>0)return true;
  return false;
}
 
vector<int> dfs(int v,int t,vector<int> f){
  if(v==t)return f;
  used[v]=true;
  for(int to=0;to<g[v].size();to++){
    int i=g[v][to];
    vector<int> &e=G[v][i];
    if(!used[i] && check(e) ){
      vector<int> d=dfs( i,t,min(f,e));
      if( d.size()==MAX && check(d) ){
        sub(G[v][i],d);
        add(G[i][v],d);
        return d;
      }
    }
  }
  return vector<int>();
}
 
vector<int> max_flow(int s,int t){
  vector<int> flow(MAX,0);
  while(1){
    memset(used,0,sizeof(used));
    vector<int> tmp(MAX,INF);
    vector<int> f=dfs(s,t,tmp);
    if(f.size()==0)return flow;
    add(flow,f);
  }
  return flow;
}
 
int m;
int t[MAX][MAX][MAX];
int u[MAX][MAX];
 
int s2i(string s){
  stringstream ss;
  int res;
  ss<<s;
  ss>>res;
  return res;
}
 
void func(int a,int b,string &tmp){
  int len=tmp.size();
  int flg=0;
  for(int i=0;i<len;i++){
    if('0'<=tmp[i]&&tmp[i]<='9')continue;
    flg=1;
  }
  if(flg==0){
    t[a][b][0]=t[b][a][0]=s2i(tmp);
    return;
  }
   
  int v,w;
  if(tmp[0]=='x')v=1;
  else{
    for(int i=0;i<len;i++){
      if(tmp[i]=='x'){
        v=s2i(tmp.substr(0,i));
        break;
      }
    }
  }
   
  if(tmp[len-1]=='x')w=1;
  else{
    for(int i=0;i<len;i++){
      if(tmp[i]=='^'){
        w=s2i(tmp.substr(i+1));
        break;
      }
    }
  }
  t[a][b][w]=t[b][a][w]=v;
}
 
int main(){
  while(1){
    cin>>n>>m;
    if(n==0&&m==0)break;
    memset(t,0,sizeof(t));
    memset(u,0,sizeof(u));
    for(int i=0;i<MAX;i++)g[i].clear();
    
    for(int i=0;i<m;i++){
      int a,b;
      string s,tmp;
      cin>>a>>b>>s;
      g[a].push_back(b);
      g[b].push_back(a);
      for(int j=0;j<(int)s.size();j++)
        if(s[j]=='+')s[j]=' ';
      stringstream ss(s);
      while(ss>>tmp){
        func(a,b,tmp);
      }
    }
 
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        G[i][j].clear();
        G[i][j].resize(MAX);
        for(int k=0;k<MAX;k++){
          G[i][j][k]=t[i][j][k];
        }
      }
    }
 
    vector<int> ans=max_flow(1,n);
    bool cnt=0;
    for(int i=MAX-1;i>=0;i--){
      if(ans[i]==0)continue;
      if(cnt>0)cout<<'+';
      cnt++;
      if(i==0||ans[i]>1)cout<<ans[i];
      if(i)cout<<'x';
      if(i>1)cout<<"^"<<i;
    }
    if(cnt==0)cout<<0;
    cout<<endl;
  }
  return 0;
}