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
/*
 * 2328.cc: Mobile Network
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100;
const int L = 50;

const int INF = 1 << 30;

/* typedef */

struct Poly {
  int as[L + 1];
  Poly() { _clear(); }
  Poly(string &s) {
    _clear();
    int pos = 0, sn = s.size();
    while (pos < sn) {
      int ai = _read_int(s, pos);
      int k = 0;
      if (pos < sn && s[pos] == 'x') {
	pos++;
	k = 1;
	if (ai == 0) ai = 1;
	if (pos < sn && s[pos] == '^') {
	  pos++;
	  k = _read_int(s, pos);
	}
      }
      as[k] = ai;
      if (pos < sn && s[pos] == '+') pos++;
    }
  }

  void _clear() { memset(as, 0, sizeof(as)); }

  int _read_int(string &s, int &pos) {
    int num = 0, sn = s.size();
    while (pos < sn && s[pos] >= '0' && s[pos] <= '9')
      num = num * 10 + s[pos++] - '0';
    return num;
  }

  bool operator<(const Poly &p) const {
    for (int i = L; i >= 0; i--)
      if (as[i] != p.as[i]) return (as[i] < p.as[i]);
    return false;
  }
  
  bool operator>(const Poly &p) const { return (p < *this); }

  Poly operator+(const Poly &p) const {
    Poly r;
    for (int i = 0; i <= L; i++) r.as[i] = as[i] + p.as[i];
    return r;
  }

  Poly operator-(const Poly &p) const {
    Poly r;
    for (int i = 0; i <= L; i++) r.as[i] = as[i] - p.as[i];
    return r;
  }

  void print() {
    bool first = true;
    for (int i = L; i >= 0; i--) {
      if (as[i]) {
	if (! first) putchar('+');
	first = false;
	if (i == 0 || as[i] > 1) printf("%d", as[i]);
	if (i) {
	  putchar('x');
	  if (i > 1) printf("^%d", i);
	}
      }
      else if (i == 0 && first) putchar('0');
    }
    putchar('\n');
  }
};

typedef queue<int> qi;
typedef pair<int,Poly> pip;
typedef vector<pip> vpip;

/* global variables */

vpip nbrs[MAX_N];
Poly minfs[MAX_N], flows[MAX_N][MAX_N], pinf, pzero;
int prvs[MAX_N];

/* subroutines */

Poly maxflow(int st, int gl) {
  memset(flows, 0, sizeof(flows));
  Poly max_flow;

  for (;;) {
    //printf("max_flow = %d, limit = %d\n", max_flow, limit);

    memset(prvs, -1, sizeof(prvs));
    prvs[st] = st;
    minfs[st] = pinf;

    qi q;
    q.push(st);

    while (! q.empty()) {
      int ui = q.front(); q.pop();

      if (ui == gl) break;
      vpip& nbru = nbrs[ui];
      for (vpip::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
        int vi = vit->first;
        Poly vc = vit->second - flows[ui][vi];
        if (prvs[vi] < 0 && vc > pzero) {
          prvs[vi] = ui;
          minfs[vi] = (minfs[ui] < vc) ? minfs[ui] : vc;
          q.push(vi);
        }
      }
    }

    if (prvs[gl] < 0) break;

    Poly min_flow = minfs[gl];
    for (int j = gl; j != st;) {
      int i = prvs[j];
      flows[i][j] = flows[i][j] + min_flow;
      flows[j][i] = flows[j][i] - min_flow;
      j = i;
    }

    max_flow = max_flow + min_flow;
  }

  return max_flow;
}

/* main */

int main() {
  pinf.as[L] = INF;

  for (;;) {
    int n, m;
    cin >> n >> m;
    if (n == 0) break;

    for (int i = 0; i < n; i++) nbrs[i].clear();
    
    for (int i = 0; i < m; i++) {
      int ai, bi;
      string ps;
      cin >> ai >> bi >> ps;
      ai--, bi--;
      Poly p(ps);

      nbrs[ai].push_back(pip(bi, p));
      nbrs[bi].push_back(pip(ai, p));
    }

    Poly mf = maxflow(0, n - 1);
    mf.print();
  }
  return 0;
}