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

Measured memory_bytes: 2232