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 <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <queue>
using namespace std;

struct Poly {
    int a[60],md;
    Poly() { md = 0,memset(a,0,sizeof(a)); }
};

Poly inf;

bool operator<(const Poly &p,const Poly &q) {
    if(p.md != q.md) return p.md < q.md;
    for(int k=p.md; k>=0; --k)
        if(p.a[k] != q.a[k]) return p.a[k] < q.a[k];
    return false;
}

Poly minPoly(const Poly p,const Poly q) {
    if(p < q) return p;
    else return q;
}

Poly operator-(const Poly &p,const Poly &q) {
    Poly ret;
    for(int k = max(p.md,q.md); k>=0; --k) {
        ret.a[k] = p.a[k] - q.a[k];
        if(ret.a[k] != 0) ret.md = max(k,ret.md);
    }
    return ret;
}

Poly operator+(const Poly &p,const Poly &q) {
    Poly ret;
    for(int k=max(p.md,q.md); k>=0; --k) {
        ret.a[k] = p.a[k] + q.a[k];
        if(ret.a[k] != 0) ret.md = max(k,ret.md);
    }
    return ret;
}

std::vector<string> splitAll(string s,string t){
  std::vector<string> v;
  for(int p=0; (p = s.find(t)) != s.npos; ){
    v.push_back(s.substr(0,p));
    s=s.substr(p+t.size());
  }
  v.push_back(s);
  return v;
}

void parseMono(string &s,Poly &poly) {
    // constant
    if(s.find("x") == s.npos) {
//        cout<<"constant "<<atoi(s.c_str())<<endl;
        poly.a[0] = atoi(s.c_str());
        return;
    }

    vector<string> r = splitAll(s,"x");

    int hoge = atoi(r[0].c_str());
    if(r[0] == "") hoge = 1;
    // linear
    if(r[1] == "") {
        poly.a[1] = hoge;
        poly.md = max(poly.md,1);
//        cout<<"linear "<<hoge<<endl;
        return;
    }

    int dim = atoi(r[1].substr(1).c_str());
//    cout<<dim<<" "<<hoge<<endl;
    poly.a[dim] = hoge;
    poly.md = max(poly.md,dim);
    return;
}

Poly parse(string s) {
    if(s.find("+") == s.npos) {
        // mono
        Poly ret;
        parseMono(s,ret);
        return ret;
    }

    vector<string> p = splitAll(s,"+");

    Poly ret;
    for(int i=0; i<p.size(); ++i) {
        if(p[i] == "") continue;
        parseMono(p[i],ret);
    }
    return ret;
}

string toStr(Poly &p) {
    string ret = "";
    bool already = false;
    if(p.md == 0 && p.a[0] == 0) {
        ret = "0";
        return ret;
    }
    stringstream ss;
    for(int k=p.md; k>=0; --k) {
        if(p.a[k] == 0) continue;
        if(already) ret += "+";
        if(k > 0) {
            if(p.a[k] > 1) {
                ss << p.a[k];
                ret += ss.str();
                ss.str("");
            }
            ret += "x";
            if(k > 1) {
                ret += "^";
                ss << k;
                ret += ss.str();
                ss.str("");
            }
        }else{
            ss << p.a[k];
            ret += ss.str();
            ss.str("");
        }
        already = true;
    }

    return ret;
}

int n,m,l;
int u,v;

Poly adj[52][52];
bool edge[52][52];

Poly maxFlow(int s,int t) {
    Poly flow[51][51];
    Poly total;

    while(1) {
        queue<int> Q;
        Q.push(s);
        vector<int> prev(51,-1);
        prev[s] = s;

        while(!Q.empty() && prev[t] < 0) {
            int u = Q.front(); Q.pop();
            for(int i=0; i<51; ++i) {
                if(!edge[u][i]) continue;
                if(prev[i] < 0 && flow[u][i] < adj[u][i]) {
//                    cout<<u<<" -> "<<i<<endl;
                    prev[i] = u;
                    Q.push(i);
                }
            }
        }

        if(prev[t] < 0) return total;
        Poly inc = inf;

        for(int j=t; prev[j] != j; j = prev[j]) {
            inc = minPoly(inc, adj[prev[j]][j]-flow[prev[j]][j]);
        }
        for(int j=t; prev[j] != j; j = prev[j])
            flow[prev[j]][j] = flow[prev[j]][j] + inc,
                flow[j][prev[j]] = flow[j][prev[j]] - inc;
        total = total + inc;
    }

    cout<<"hoge"<<endl;
    return Poly();
}

int main() {
    inf.md = 59;
    for(int k=inf.md; k>=0; --k) inf.a[k] = 1<<29;
    while(cin>>n>>m, n|m) {
        for(int i=0; i<51; ++i)
            for(int j=0; j<51; ++j) {
                adj[i][j] = adj[j][i] = Poly();
                edge[i][j] = edge[j][i] = false;
            }
        string s;
        for(int i=0; i<m; ++i) {
            cin>>u>>v>>s;
//            cout<<s<<endl;
            Poly p = parse(s);
            adj[u][v] = adj[v][u] = p;
            edge[u][v] = edge[v][u] = true;
//            cout<<toStr(p)<<endl;
            // for(int j=0; j<50; ++i) cout<<p.a[j]<<" ";
            // cout<<endl;
        }
//        cin>>u>>v;
        Poly p = maxFlow(1,n);

//        cout<<"Case "<<n<<" "<<m<<endl;
        cout<<toStr(p)<<endl;
    }
}