#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

typedef int Weight;
struct Edge {
  int src, dst;

  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

bool resflag[50][50];

#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])
Weight edmonds_karp(Graph &g, int s, int t) {
  int n = g.size();
  Matrix flow(n, Array(n)), capacity(n, Array(n));
  REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight;
  
  Weight total = 0;
  while(1) {
    queue<int> Q; Q.push(s);
    vector<int> prev(n, -1); prev[s] = s;
    while(!Q.empty() && prev[t] < 0) { // s ツつゥツづァ t ツづ鳴猟ャツつケツづゥツ路ツづーBFSツづ個ゥツづつつッツづゥツ。
      int u = Q.front(); Q.pop();
      REP(v, n) if (prev[v] < 0 && RESIDUE(u, v) > 0) { // Spaghetti Source ツづ陛渉つヲツつスツ。
        prev[v] = u;
        Q.push(v);
      }
    }
    if (prev[t] < 0) break;
    Weight inc = INF;
    for (int j=t; prev[j]!=j; j=prev[j])
      inc = min(inc, RESIDUE(prev[j], j));
    for (int j=t; prev[j]!=j; j=prev[j])
      flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc; // ツ逆ツ陛督づ掲low ツつゥツづァツ暗クツつュツつアツづづ可淞つオツ姪淞つケツづゥツづヲツつ、ツづ可つキツづゥツ。
    // ツづつづ慊づィツ、flow ツつェツ猟ャツづェツつスツづつアツづォツづ個逆ツ古シツつォツづ個陛督づ可甘鳴つオツづСESIDUE ツつェツつサツづ個閉ェツ妥・ツつォツつュツづ按づゥツ。
    total += inc;
  }
  REP(i, n) {
    REP(j, i) {
      if (RESIDUE(i,j)&&RESIDUE(j,i)) {
        resflag[i][j] = 1;
        resflag[j][i] = 1;
      }
    }
  }
  return total;
}
typedef pair<int,int> pii;
pii func(string s) {
  int a, b=INF;
  REP(i, s.size()) {
    if (s[i]=='x') {
      if(i==0) {
        b = 1;
      } else {
        b = atoi(s.substr(0, i).c_str());
      }
      if (s[i+1]=='^') {
        a = atoi(s.substr(i+2).c_str());
      } else {
        a = 1;
      }
    }
  }
  if (b == INF) {
    b = atoi(s.c_str());
    a = 0;
  }
  return pii(a,b);
}
void parse(string s, int *arr) {
  int last = 0;
  REP(i, s.size()) {
    if (s[i] == '+') {
      pii p = func(s.substr(last, i-last));
      arr[p.first] = p.second;
      last = i+1;
    }
  }
  pii p = func(s.substr(last));
  arr[p.first] = p.second;

  // cout << s << endl;
  // REP(i, 51) {
  //   cout << arr[i] << " ";
  // }
  // cout << endl;
}

int main() {
  int n,m;
  while(cin>>n>>m,n||m) {
    int a[m][51];
    memset(a, 0, sizeof(a));
    int s[m], t[m];
    REP(i, m) {
      cin >> s[i] >> t[i];
      s[i]--; t[i]--;
      string ss;
      cin >> ss;
      parse(ss, a[i]);
    }
    int res[51];
    memset(resflag, 0, sizeof(resflag));
    for (int i=50; i>=0; --i) {
      Graph g(n);
      REP(j, m) {
        int wei = a[j][i];
        if (resflag[s[j]][t[j]]) {
          wei = INF;
        }
        g[s[j]].push_back(Edge(s[j], t[j], wei));
        g[t[j]].push_back(Edge(t[j], s[j], wei));
      }
      res[i] = edmonds_karp(g, 0, n-1);
      //cout << res[i] << endl;
    }
    string ans;
    bool f = 0;
    for (int i=50; i>=0; --i) {
      if (res[i]) {
        if (f) ans+="+";
        f = 1;
        stringstream ss;
        ss<<res[i];
        if (res[i] > 1 || i==0)
          ans+=ss.str();
        if (i>=2) {
          stringstream ss2;
          ss2<<i;
          ans+="x^"+ss2.str();
        } else if(i==1)
          ans += "x";
      }
    }
    if (!f) {
      ans = "0";
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 0