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<iostream>
#include<sstream>
#include<queue>
using namespace std;
const int N = 51;

class E{
public:
  int a[N];
  E(){
    for(int i=0;i<N;i++)a[i]=0;
  }
  E(int n){
    for(int i=0;i<N;i++)a[i]=0;
  }
  E(int n,int val){
    for(int i=0;i<N;i++)a[i]=val;
  }
  E(int n,int v,int s){
    for(int i=0;i<N;i++)a[i]=0;
    a[0]=1;
  }
  E operator+(const E &c)const{
    E ret(N);
    for(int i=0;i<N;i++)ret.a[i]=a[i]+c.a[i];
    return ret;
  }
  E operator-(const E &c)const{
    E ret(N);
    for(int i=0;i<N;i++)ret.a[i]=a[i]-c.a[i];
    return ret;
  }
  E& operator+=(const E &b){
    for(int i=0;i<N;i++)a[i]+=b.a[i];
    return *this;
  }
  E& operator-=(const E &b){
    for(int i=0;i<N;i++)a[i]-=b.a[i];
    return *this;
  }
  bool operator<(const E & b)const{
    for(int i=N-1;i>=0;i--)if (a[i] != b.a[i])return a[i] < b.a[i];
    return false;
  }
  bool operator>(const E &b)const{
    for(int i=N-1;i>=0;i--){
      if (a[i] != b.a[i])return a[i] > b.a[i];
    }
    return false;
  }
  bool operator==(const E &b)const{
    for(int i=0;i<N;i++)if (a[i] != b.a[i])return false;
    return true;
  }
  void op(){
    bool isf=true;
    for(int i=N-1;i>=1;i--){
      if (a[i] == 0)continue;
      if (a[i] > 0){
        if (!isf)cout <<"+";
        if (a[i] > 1)cout << a[i];
      }else {
        if (a[i] == -1)cout <<"-";
        else cout << a[i];
      }
      cout <<"x";
      if (i > 1)cout <<"^"<< i; 
      isf=false;
    }
    if (isf)cout << a[0];
    else if (a[0] != 0){
      if (a[0] > 0)cout <<"+" << a[0];
      if (a[0] < 0)cout << a[0];
    }
    cout << endl;
  }
};

E parse(string &in){
  E ret(N);
  int p=0;
  while(p < (int)in.size()){
    int neg=1;
    int a=0,x=0;
    if (in[p] == '+')p++;
    if (in[p] == '-')neg=-1,p++;
    if (isdigit(in[p])){
      while(p < (int)in.size() && isdigit(in[p]))
        a=a*10+in[p++]-'0';
    }else a=1;
    
    if (in[p] == 'x'){
      p++;
      if (in[p] != '^')x=1;
      else p++;
      while(p < (int)in.size() && isdigit(in[p]))x=x*10+in[p++]-'0';
    }
    ret.a[x]=a;
    ret.a[x]*=neg;
  }
  return ret;
}

const int MAX = 100;
const E ZERO(N);
const E INF(N,(1<<25));
const E ONE(N,1,1);
E cap[MAX][MAX];
bool vis[MAX];
int parent[MAX];
E flow[MAX][MAX];
int layer[MAX]; 

void make_layer(int n,int s,int t){
  queue<int> Q;
  Q.push(s);
  layer[s]=0;
  while(!Q.empty()){
    int now = Q.front();Q.pop();
    for(int i=0;i<n;i++){
      if (cap[now][i]-flow[now][i] > ZERO && layer[i] == -1){
        layer[i] = layer[now]+1;
        Q.push(i);
      }
    }
  }
}

E augment(int now,int t,int n,E f){
  if (now == t || f == ZERO)return f;
  if (vis[now])return ZERO;
  vis[now]=true;
  for(int i=0;i<n;i++){
    if (layer[now] < layer[i]){
      E tmp = augment(i,t,n,min(f,cap[now][i]-flow[now][i]));
      if (tmp > ZERO){
        flow[now][i]+=tmp;
        flow[i][now]=ZERO-flow[now][i];
        vis[now]=false;
        return tmp;
      }      
    }
  }
  return ZERO;
}

void dinic(int n,int s,int t){
  E ansflow=ZERO;
  bool flag=true;
  for(int i=0;i<n;i++)for(int j=0;j<n;j++)flow[i][j]=ZERO;
  while(flag){
    fill(layer,layer+n,-1);
    fill(vis,vis+n,false);
    make_layer(n,s,t);
    if (layer[t] == -1)break;
    
    for(E f=ZERO;;flag=true){
      f=augment(s,t,n,INF);
      bool fg=false;
      for(int i=0;i<N;i++)if (f.a[i]!=0)fg=true;
      if (!fg)break;
      ansflow+=f;
    }
  }
  ansflow.op();
}

int main(){
  int n,m;
  while(cin>>n>>m && n){
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        cap[i][j]=ZERO;
    for(int i=0;i<m;i++){
      int f,t;
      string tmp;
      cin>>f>>t>>tmp;
      f--;t--;
      E a=parse(tmp);
      cap[f][t]+=a;
      cap[t][f]+=a;
    }
    dinic(n,0,n-1);
  }
}