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



Measured memory_bytes: 3280