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<cstdlib>
#include<map>
#include<utility>
#include<vector>
#include<string>

using namespace std;

struct edge{
  int to,cap,rev;
};

vector<edge> G[52];
bool used[52];

void add_edge(int from,int to,int cap){
  G[from].push_back({to,cap,(int)G[to].size()});
  G[to].push_back({from,cap,(int)G[from].size()-1});
}

int dfs(int v,int t,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]&&e.cap>0){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
	e.cap-=d;
	G[e.to][e.rev].cap+=d;
	return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow=0;
  for(;;){
    fill(begin(used),end(used),false);
    int f=dfs(s,t,1e9);
    if(f==0)return flow;
    flow+=f;
  }
}

int main(){
  for(int N,M;cin>>N>>M,N|M;){
    bool nz=false;
    map<pair<int,int>,vector<int> >pols;
    for(int i=0;i<M;i++){
      int u,v;
      char p[1234];
      cin>>u>>v>>p;
      vector<int> c(51);
      for(char *pp=p;*pp;){
	pp+=*pp=='+';
	int cc=1;
	if(*pp!='x'){
	  cc=strtol(pp,&pp,10);
	}
	int f=0;
	if(*pp){
	  pp++;
	  f=1;
	  if(*pp=='^'){
	    f=strtol(pp+1,&pp,10);
	  }
	}
	c[f]=cc;
      }
      pols[make_pair(u,v)]=c;
    }
    for(int i=50;i>=0;i--){
      for(auto &e:G){
	e.clear();
      }
      for(auto e:pols){
	add_edge(e.first.first,e.first.second,e.second[i]);
      }
      int f=max_flow(1,N);
      if(f){
	if(nz){
	  cout<<'+';
	}
	nz=true;
	if(f>1||i==0){
	  cout<<f;
	}
	if(i){
	  cout<<'x';
	  if(i>1){
	    cout<<'^'<<i;
	  }
	}
      }
      for(int j=1;j<=N;j++){
	for(auto e:G[j]){
	  auto k=make_pair(j,e.to);
	  if(pols.count(k)&&e.cap!=0&&e.cap!=pols[k][i]*2){
	    for(int l=i;l>=0;l--){
	      pols[k][l]=1e9;
	    }
	  }
	}
      }
    }
    if(!nz){
      cout<<0;
    }
    cout<<endl;
  }
}

	
	