#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;
}

Measured memory_bytes: 1892