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 <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct capacity {
  vector<int> val;
  capacity():val(55, 0){}
  capacity(vector<int> ini):val(ini){}
  capacity operator + (capacity r) {
    vector<int> res(55);
    for(int i = 0; i < 55; i++) res[i] = val[i] + r.val[i];
    return capacity(res);
  }
  capacity operator - (capacity r) {
    vector<int> res(55);
    for(int i = 0; i < 55; i++) res[i] = val[i] - r.val[i];
    return capacity(res);
  }
  capacity operator * (int k) {
    vector<int> res(55);
    for(int i = 0; i < 55; i++) res[i] = val[i] * k;
    return capacity(res);
  }
  capacity& operator - () {
    for(int i = 0; i < 55; i++) val[i] = -val[i];
    return *this;
  }
  bool operator == (const capacity& r) const {
    return val == r.val;
  }
  bool operator < (const capacity& r) const {
    vector<int> x = val, y = r.val;
    reverse(all(x));
    reverse(all(y));
    return x < y;
  }
  bool operator > (const capacity& r) const {
    vector<int> x = val, y = r.val;
    reverse(all(x));
    reverse(all(y));
    return x > y;
  }
};

const capacity INF = capacity(vector<int>(55, inf));
const capacity ZERO = capacity(vector<int>(55, 0));

struct Dinic {
  struct edge {
    int to, rev;
    capacity cap;
    edge(){}
    edge(int to, capacity cap, int rev)
      :to(to), cap(cap), rev(rev){}
  };
  vector< vector<edge> > graph;
  vector<int> level, iter;
  Dinic(){}
  Dinic(int V):graph(V), level(V), iter(V){}
  void add_edge(int from, int to, capacity cap) {
    graph[from].emplace_back(to, cap, graph[to].size());
    graph[to].emplace_back(from, ZERO, graph[from].size()-1);
  }
  void bfs(int s) {
    fill(all(level), -1);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(que.size()) {
      int v = que.front(); que.pop();
      for(int i = 0; i < graph[v].size(); i++) {
	edge& e = graph[v][i];
	if(e.cap > ZERO && level[e.to] < 0) {
	  level[e.to] = level[v] + 1;
	  que.push(e.to);
	}
      }
    }
  }
  capacity dfs(int v, int t, capacity f) {
    if(v == t) return f;
    for(int& i = iter[v]; i < graph[v].size(); i++) {
      edge& e = graph[v][i];
      if(e.cap > ZERO && level[v] < level[e.to]) {
	capacity d = dfs(e.to, t, min(f, e.cap));
	if(d > ZERO) {
	  e.cap = e.cap - d;
	  graph[e.to][e.rev].cap = graph[e.to][e.rev].cap + d;
	  return d;
	}
      }
    }
    return ZERO;
  }
  capacity max_flow(int s, int t) {
    capacity flow = ZERO;
    while(1) {
      bfs(s);
      if(level[t] < 0) return flow;
      fill(all(iter), 0);
      capacity f; while((f = dfs(s, t, INF)) > ZERO) flow = flow + f;
    }
  }
};

capacity to_cap(string s) {
  vector<char> vec;
  s += '+';
  for(char c : s) {
    if(c == '+') {
      if(vec.back() == 'x') vec.push_back('^'), vec.push_back('1');
      else if(isdigit(vec.back())) {
 	if(vec.size() == 1 || (vec.size() > 1 && vec[vec.size()-2] != '^')) {
 	  vec.push_back('x');
 	  vec.push_back('^');
 	  vec.push_back('0');
 	}
      }
    }
    else if(c == 'x' && (vec.empty() || vec.back() == '+')) vec.push_back('1');
    vec.push_back(c);
  }
  vec.pop_back();
  string t = "";
  for(char c : vec) t += c;
  vector<int> cap(55, 0);
  char buf[1024], a[1024], b[1024];
  strcpy(buf, t.c_str());
  int of = 0;
  while(sscanf(buf + of, "%[^x]x^%[^+]", a, b) != EOF) {
    of += strlen(a) + 2 + strlen(b);
    cap[atoi(b)] = atoi(a);
  }
  return capacity(cap);
}

string to_str(capacity cap) {
  string res = "";
  bool flag = false;
  rep(i, cap.val.size()) {
    if(cap.val[i] != 0) {
      string tmp = (i && cap.val[i] == 1 ? "" : to_string(cap.val[i]));
      if(i > 0) tmp += "x";
      if(i > 1) tmp += "^"+to_string(i);
      if(flag) tmp = tmp + "+";
      res = tmp + res;
      flag = true;
    }
  }
  return (res == "" ? "0" : res);
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, M;
  while(cin >> N >> M, N || M) {
    Dinic graph(N);
    rep(i, M) {
      int u, v;
      string p;
      cin >> u >> v >> p;
      --u, --v;
      capacity c = to_cap(p);
      // rep(j, 4) cout << c.val[j] << " ";
      // cout << endl;
      graph.add_edge(u, v, c);
      graph.add_edge(v, u, c);
    }
    capacity res = graph.max_flow(0, N-1);
    //cout << "rem" << endl;
    // rep(i, graph.graph.size()) {
    //   cout << i << " : " << endl;
    //   rep(j, graph.graph[i].size()) {
    //  	cout << graph.graph[i][j].to << "\\";
    //  	rep(k, 5) cout << graph.graph[i][j].cap.val[k] << " ";
    //  	cout << endl;
    //   }
    //   cout << endl;
    // }
    //cout <<"ans" << endl;
    //rep(j, 4) cout << res.val[j] << " ";
    //cout << endl;
    cout << to_str(res) << endl;
  }

  return 0;
}