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<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;


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){}
    };
    
    T INF;
    vector<vector<edge> > G;
    vector<int> level,iter;
    
    Dinic(){}
    Dinic(int n,T INF):INF(INF),G(n),level(n),iter(n){}
    
    pll add_edge(int from,int to,int cap){
        G[from].emplace_back(to,cap,G[to].size());
        G[to].emplace_back(from,directed?0:cap,G[from].size()-1);
        return {G[from].size()-1,G[to].size()-1};
    }
    
    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,INF);
    }
};

const ll MX=1LL<<30;

bool number(char c){return '0'<=c && c<='9';}

void toNum(string &s,vector<ll> &ret){
    ll k=0;
    for(int t=0;t<s.size();t++){
        if(s[t]=='x'){
            ll z=0;
            while(t<s.size() && s[t]!='+'){
                if(number(s[t])){z*=10; s[t]-='0'; z+=s[t];}
                ++t;
            }
            ret[max(z,1LL)]=max(k,1LL);
            k=0;
            continue;
        }
        else{
            k*=10;
            s[t]-='0';
            k+=s[t];
        }
    }
    ret[0]=k;
}

void toStr(vector<ll> &ans){
    while(ans.size()>0 && ans.back()==0){ans.pop_back();}
    ll last=0;
    while(last<ans.size() && ans[last]==0){last++;}
    if(last==ans.size()){cout<<0<<endl; return;}
    for(ll i=ans.size()-1;i>=last;i--){
        if(ans[i]==0){continue;}
        if(ans[i]!=1 || i==0){cout<<ans[i];}
        if(i>0){cout<<"x";}
        if(i>1){cout<<"^"<<i;}
        if(i!=last){cout<<"+";}
    }
    cout<<endl;
}

int main(){
    ll n,m;
    while(cin>>n>>m){
        if(n==0){break;}
    vector<pll> Edge(m);
    vector<vector<ll>> Cost(m,vector<ll>(51,0));
    vector<pll> num(m);
    for(int i=0;i<m;i++){
        cin>>Edge[i].F>>Edge[i].S;
        Edge[i].F--; Edge[i].S--;
        if(Edge[i].F>Edge[i].S){swap(Edge[i].F,Edge[i].S);}
        string s;
        cin>>s;
        toNum(s,Cost[i]);
    }
    vector<ll> ans(51,0);
    Dinic<ll,false> Flow(n,MX);
    for(int i=0;i<m;i++){
        num[i]=Flow.add_edge(Edge[i].F,Edge[i].S,0);
    }
    for(ll time=50;time>=0;time--){
        for(int i=0;i<m;i++){
            if(Flow.G[Edge[i].F][num[i].F].cap>0){Flow.G[Edge[i].F][num[i].F].cap=MX;}
            if(Flow.G[Edge[i].S][num[i].S].cap>0){Flow.G[Edge[i].S][num[i].S].cap=MX;}
        }
        for(int i=0;i<m;i++){
            Flow.G[Edge[i].F][num[i].F].cap+=Cost[i][time];
            Flow.G[Edge[i].S][num[i].S].cap+=Cost[i][time];
        }
        ans[time]=Flow.flow(0,n-1);
    }
    toStr(ans);
    }
    
    return 0;
}

