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;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using vi = vector<int>;

// (?????????,??????,??????)
struct edge{
    int to;
    vi cap;
    int rev;
};

const int MAX_V = 50; // TODO:initialize
const vi F_INF = vi(51,19191919); // TODO:initialize
vector<edge> G[MAX_V];
int level[MAX_V]; // s??????????????¢
int iter[MAX_V]; // ???????????§??????????????£??????

void show(vi f)
{
    string ans = "";
    for(int i=50; i>0; --i)if(f[i]!=0)
    {
        if(f[i]>0) ans += "+";
        else ans += "-";

        if(abs(f[i])>1) ans += to_string(abs(f[i]));

        if(i>0)
        {
            ans += "x";
            if(i>1) ans += "^" + to_string(i);
        }
    }

    if(f[0]!=0)
    {
        if(f[0]>0) ans += "+";
        else ans += "-";
        ans += to_string(abs(f[0]));
    }

    if(ans=="") ans = "0";
    if(ans[0]=='+') ans = ans.substr(1);
    cout << ans << endl;
}

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

inline bool positive(vi v)
{
    for(int i=50; i>=0; --i)if(v[i]!=0) return v[i]>0;
    return false;
}

inline vi ADD(vi a, vi b)
{
    vi ret(51);
    rep(i,51) ret[i]=a[i]+b[i];
    return ret;
}

inline vi SUB(vi a, vi b)
{
    vi ret(51);
    rep(i,51) ret[i]=a[i]-b[i];
    return ret;
}

inline vi vi_min(vi a, vi b)
{
    for(int i=50; i>=0; --i)
    {
        int d = a[i]-b[i];
        if(d>0) return b;
        else if(d<0) return a;
    }
    return a;
}

void dinic_bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        rep(i,G[v].size()){
            edge &e = G[v][i];
            if(positive(e.cap) && level[e.to]<0){
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

// ?¢?????????????dfs??§??¢???
vi dinic_dfs(int v, int t, vi f){
    if(v==t) return f;
    for(int &i=iter[v]; i<G[v].size(); ++i){
        edge &e=G[v][i];
        if(positive(e.cap) && level[v]<level[e.to]){
            vi d = dinic_dfs(e.to,t,vi_min(f,e.cap));
            if(positive(d)){
                e.cap = SUB(e.cap,d);
                G[e.to][e.rev].cap = ADD(G[e.to][e.rev].cap,d);
                return d;
            }
        }
    }
    return vector<int>(51,0);
}

// s??????t???????????§???
vi max_flow(int s, int t){
    vi flow(51);
    while(1){
        dinic_bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        vi f;
        while( positive(f=dinic_dfs(s,t,F_INF)) ) flow = ADD(flow,f);
    }
}

vector<string> split(const string &s, char d)
{
    vector<string> ret;
    stringstream ss(s);
    string item;
    while(getline(ss,item,d))
    {
        if(!item.empty()) ret.pb(item);
    }
    return ret;
}

vi convert(string s)
{
    vi ret(51);
    for(const auto &t:split(s,'+'))
    {
        int idx = t.find("x");
        if(idx==-1) ret[0]=atoi(t.c_str());
        else
        {
            int n = 1;
            if(idx+2<t.size())
            {
                string i=t.substr(idx+2);
                n = atoi(i.c_str());
            }

            string a=t.substr(0,idx);
            int val = 1;
            if(a.size()) val = atoi(a.c_str());

            ret[n] = val;
        }
    }
    return ret;
}

int main()
{
    int n,m;
    while(cin >>n >>m,n)
    {
        rep(i,MAX_V) G[i].clear();
        rep(i,m)
        {
            int u,v;
            string s;
            cin >>u >>v >>s;
            add_edge(u-1,v-1,convert(s));
        }
        show(max_flow(0,n-1));
    }
    return 0;
}