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>
#define int long long
#define INF 1e9
#define MAX_V 505
using namespace std;
/*?????§?????¢?????´?????????(Ford_Fulerson????????¨)???O(F|E|)*/

//????????¨????§???????(???????????????????????????)
struct edge{
  int to;
  vector<int> cap;
  int rev;
};

vector<edge> G[MAX_V]; //??°???????????£??\?????????
bool used[MAX_V];      //DFS??§?????§??????????????????????????°

//from??????to??????????????????cap???????????°?????????????????????
void add_edge(int from,int to,vector<int> &cap){
  G[from].push_back((edge){to,cap,(int)G[to].size()});
  G[to].push_back((edge){from,vector<int>((int)cap.size(),0),(int)G[from].size()-1});  
}

bool check(vector<int> &A){
  for(int i=0;i<A.size();i++)
    if(A[i]!=0) return A[i]>0;
  return false;
}

bool check2(vector<int> &A){
  for(int i=0;i<A.size();i++)
    if(A[i]==INF) return false;
  return true;
}

void Minus(vector<int> &res, vector<int> &v){
  for(int i=0;i<res.size();i++) res[i]-=v[i];
}

void Plus(vector<int> &res, vector<int> &v){
  for(int i=0;i<res.size();i++) res[i]+=v[i];
}

vector<int> Min(vector<int> &A, vector<int> &B){
  for(int i=0;i<A.size();i++){
    if(A[i]<B[i]) return A;
    if(A[i]>B[i]) return B;
  }
  return A;
}

//?¢?????????????DFS??§??¢???
vector<int> dfs(int v,int t,vector<int> f){
  if(v == t)return f;
  used[v]=true;
  for(int i=0; i<G[v].size() ;i++){
    edge &e = G[v][i];
    if(!used[e.to] && check(e.cap) ){
      vector<int> d = dfs(e.to ,t , Min(f,e.cap));
      if(check(d)&&check2(d)){
	Minus(e.cap, d);
	Plus(G[e.to][e.rev].cap, d);
	return d;
      }
    }
  }
  return vector<int>((int)f.size(),0);
}

bool isall0(vector<int> &v){
  for(int i=0;i<v.size();i++)
    if(v[i]!=0) return false;
  return true;
}

int V=55;

//s??????t???????????§???????±???????
vector<int> max_flow(int s,int t){
  vector<int> flow = vector<int>(V,0);
  for(;;){
    memset(used,0,sizeof(used));
    vector<int> f = dfs(s, t, vector<int>(V,INF));
    if(isall0(f)) return flow;
    Plus(flow, f);
  }
}

vector<int> tov(string s){
  
  vector<int> res = vector<int>(V,0);
  
  int num1, num2, p=0;
  
  if('0'<=s[p]&&s[p]<='9'){
    num1=0;
    while('0'<=s[p]&&s[p]<='9') num1=num1*10+s[p++]-'0';
  }else num1=1;
  
  if(p==s.size()){
    num2=0;
  }else{
    if(p+1==s.size()) num2=1;
    else{
      //assert(s[p+1]=='^'&&('0'<=s[p+2]&&s[p+2]<='9'));
      p+=2;
      num2=0;
      while('0'<=s[p]&&s[p]<='9') num2=num2*10+s[p++]-'0';
    }
  }
  
  res[num2]=num1;
  
  return res;
}

vector<int> tocap(string s){
  
  vector<int> res = vector<int>(V,0);
  s+='+';
  
  string t;
  
  for(int i=0;i<s.size();i++){
    if(s[i]=='+'){
      vector<int> r=tov(t);
      Plus(res,r);
      t="";
    }else t+=s[i];
  }
  
  reverse(res.begin(), res.end());
  
  return res;
}

string itos(int num){

  string res;
  
  while(num){
    res=(char)(num%10+'0')+res;
    num/=10;
  }
  
  return res;
}

void output(vector<int> ans){
  
  reverse(ans.begin(), ans.end());
  
  string s;
  int flag=0;
  
  for(int i=ans.size()-1;i>=0;i--){
    if(ans[i]==0) continue;
    if(flag) s+="+";
    flag=1;
    if(i==0||(i!=0&&ans[i]!=1)) s+=itos(ans[i]);
    if(i==1) s+="x";
    else if(i) s+="x^", s+=itos(i);
  }
  if(s=="") s="0";
  cout<<s<<endl;
}

signed main(){
    
  int n, m;

  while(1){
    
    cin>>n>>m;
    if(!n&&!m) break;
    
    int a, b;
    string s;
    
    for(int i=0;i<m;i++){
      cin>>a>>b>>s;
      vector<int> cap=tocap(s);
      add_edge(a-1,b-1,cap);
      add_edge(b-1,a-1,cap);
    }
    
    output(max_flow(0,n-1));
    
    for(int i=0;i<MAX_V;i++) G[i].clear();
  }
  
  return 0;
}