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
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <deque>

#define LL long long
#define DB double
#define SI(a) scanf("%d",&a)
#define SD(a) scanf("%lf",&a)
#define SS(a) scanf("%s",a)
#define PF printf
#define MM(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a;i<b;i++)
#define REPD(i,a,b) for(int i=a;i>b;i--)
#define INF 0x3f3f3f3f
#define EPS 1e-8
#define bug puts("bug")
using namespace std;
const int N = 55;
int re[N][N][55];
int res[N][N];
int n,m;
void ini()
{
    MM(re,0);
    MM(res,0);
}
void oper_i(char a[],int &e,int &f)
{
    int flag = 0,flag1 = 0;
    int len = strlen(a);
    REP(i,0,len)
    {
        if(a[i]=='x')
            flag = 1;
        if(a[i]=='^')
            flag1 = 1;
    }
    if(flag == 0)
    {
        e = 0;
        sscanf(a,"%d",&f);
        return;
    }
    if(flag1 == 1)
    {
        if(a[0]=='x')
        {
            f = 1;
            sscanf(a,"x^%d",&e);
            return;
        }
        sscanf(a,"%dx^%d",&f,&e);
        return;
    }else
    {
        if(a[0]=='x')
        {
            f = 1;e = 1;
            return;
        }
        sscanf(a,"%dx",&f);
        e = 1;
        return;
    }
}
void oper(char ch[],int c[])//
{
    REP(i,0,51) c[i] = 0;
    char tmp[50];
    int j=0,len = strlen(ch);
    int e,f;
    REP(i,0,len+1)
    {
        if(ch[i]=='+'||ch[i]=='\0'||ch[i]=='\n')
        {
            tmp[j] = '\0';
            oper_i(tmp,e,f);
            //cout<<f<<"^"<<e<<endl;
            c[e] += f;
            j = 0;
        }else
        {
            tmp[j] = ch[i];
            j++;
        }
    }
}

int g[N][N],gap[N],dist[N],pre[N],cur[N];
///s1->t1 size{1...n}
int sap(int s1,int t1,int n)
{
    int ret = 0,aug = INF,u,v;
    memset(gap,0,sizeof(gap));
    memset(dist,0,sizeof(dist));
    for(int i=0;i<=n;i++) cur[i] = 1;
    u = pre[s1] = s1;
    gap[0] = n;
    while(dist[s1]<=n){
    loop:
        for(v = cur[u];v<=n;v++)
        if(g[u][v]>0&&dist[u] ==dist[v]+1)
        {
            cur[u] = v;aug = min(aug,g[u][v]);
            pre[v] = u;
            u = v;
            if(u==t1){
                ret+=aug;
                for(u=pre[u];v!=s1;v=u,u=pre[u])
                g[u][v]-=aug,g[v][u]+=aug;
                aug = INF;
            }
            goto loop;
        }
        int mind =n;
        for(v=1;v<=n;v++)
        	if(g[u][v]>0&&mind>dist[v])
        	mind = dist[v],cur[u] = v;
        if(--gap[dist[u]]<=0) break;
        gap[dist[u]=mind+1]++;
        u=pre[u];
    }return ret;
}
void solve()
{
    int ans[109];
    MM(ans,0);
    REPD(t,50,-1)
    {
        REP(i,1,n+1)
        REP(j,1,n+1)
        {
            if(res[i][j])
                g[i][j] = INF;
            else
                g[i][j] = re[i][j][t];
        }
        ans[t] = sap(1,n,n);
        //if(ans[t]>0)
        //cout<<t<<" "<<ans[t]<<endl;
        REP(i,1,n+1)
        REP(j,1,n+1)
        if(res[i][j]==0&&re[i][j][t])
        {
            if(g[i][j]>0)
            {
                res[i][j] = 1;
                //cout<<i<<"---"<<j<<endl;
            }
            else
            {
                REP(k,1,n+1)
                REP(l,1,n+1)
                {
                    if(res[k][l])
                        g[k][l] = INF;
                    else
                        g[k][l] = re[k][l][t];
                }
                g[i][j] -= 1;
                if(ans[t]==sap(1,n,n))
                {
                    res[i][j] = 1;
                    //cout<<i<<"---"<<j<<endl;
                }
            }
        }
    }

    int flag = 0;
    REPD(i,50,-1)
    {
        if(ans[i])
        {
            if(flag) printf("+");
            flag = 1;
            if(i>1)
            {
                if(ans[i]==1)
                    printf("x^%d",i);
                else
                    printf("%dx^%d",ans[i],i);
            }else if(i==1)
            {
                if(ans[i]==1)
                    printf("x");
                else
                    printf("%dx",ans[i]);
            }else
            {
                printf("%d",ans[i]);
            }
        }
    }
    if(flag==0) printf("0");
    printf("\n");
}
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    int tmp[100];
    while(1)
    {
        SI(n),SI(m);
        if(n==0&&m==0) break;
        ini();

        int a,b;
        char ch[1024];
        REP(i,0,m)
        {
            SI(a),SI(b);
            SS(ch);
            oper(ch,tmp);
            REP(j,0,51)
            if(tmp[j])
            {
                re[a][b][j]+=tmp[j];
                re[b][a][j]+=tmp[j];
            }
        }
        solve();
    }
    return 0;
}