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