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 REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
typedef long long ll;

#define MAX_V (55)
#define INF (1<<29)

const vector<int> zero_cap = vector<int>(51);
const vector<int> inf_flow = vector<int>(51, INF);

struct edge {
  int to, rev;
  vector<int> cap;
  edge(int to, vector<int> cap, int rev) : to(to), cap(cap), rev(rev) {
    assert(cap.size() == 51);
  }
};

vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from, int to, vector<int> cap) {
  G[from].push_back(edge(to, cap, G[to].size()));
  G[to].push_back(edge(from, zero_cap, G[from].size() - 1));
}

bool larger_than_0(vector<int> const& a) {
  rep(i, a.size()) if(a[i] > 0) return 1;
  return 0;
}

vector<int> min(vector<int> const& a, vector<int> const& b) {
  for(int i=50; i>=0; i--) {
    if(a[i] == b[i]) continue;
    if(a[i] < b[i]) return a;
    return b;
  }
  return a;
}

void assign_minus(vector<int>& v, vector<int> const& r) {
  for(int i=50; i>=0; i--) {
    v[i] -= r[i];
  }
}

void assign_plus(vector<int>& v, vector<int> const& r) {
  for(int i=50; i>=0; i--) {
    v[i] += r[i];
  }
}

vector<int> dfs(int v, int t, vector<int> f) {
  if(v == t) return f;
  used[v] = 1;
//  cout << "v = " << v << endl;
  rep(i, G[v].size()) {
    edge& e = G[v][i];
    if(!used[e.to] && larger_than_0(e.cap)) {
      auto d = dfs(e.to, t, min(f, e.cap));
      if(larger_than_0(d)) {
        assign_minus(e.cap, d);
        assign_plus(G[e.to][e.rev].cap, d);
        return d;
      }
    }
  }

  return zero_cap;
}

vector<int> max_flow(int s, int t) {
  vector<int> flow = zero_cap;
  for(;;) {
    memset(used, 0, sizeof(used));
    auto f = dfs(s, t, inf_flow);
    if(f == zero_cap) return flow;
    assign_plus(flow, f);
  }
}

void init() {
  rep(i, MAX_V) G[i].clear();
}

int N, M;

typedef string::const_iterator Iter;
Iter it;

int number() {
  int ret = 0;
  assert(isdigit(*it));
  while(isdigit(*it)) {
    ret *= 10; ret += *it - '0';
    it++;
  }
  return ret;
}

vector<string> split(string& s) {
  int n = s.size();
  int prev = 0;
  vector<string> ret;
  rep(i, n) {
    if(s[i] == '+') {
      ret.push_back(string(s.begin() + prev, s.begin() + i));
      prev = i + 1;
    }
  }
  ret.push_back(string(s.begin() + prev, s.end()));
  return ret;
}

int get_coef(string& term) {
  assert(!term.empty());
  if(term[0] == 'x') return 1;
  int n = term.size();
  rep(i, n) {
    if(term[i] == 'x') {
      return stoi(string(term.begin(), term.begin() + i));
    }
  }
  return stoi(term);
}

int get_expo(string& term) {
  if(term.find('x') == string::npos) return 0;
  if(term.find('^') == string::npos) return 1;
  int n = term.size();
  string expos;
  for(int i=n-1; i>=0; i--) {
    if(term[i] == '^') break;
    expos += term[i];
  }
  reverse(expos.begin(), expos.end());
  return stoi(expos);
}

vector<int> change_poly(string& s) {
  vector<int> ret(51);
  auto v = split(s);
  for(auto && e: v)
    ret[get_expo(e)] = get_coef(e);
  return ret;
}

void output(vector<int>& ans) {
  bool first = 0;
  for(int i=50; i>=0; i--) {
    if(ans[i] > 0) {
      if(first) cout << '+';
      first = 1;
      if(ans[i] > 1 || (ans[i] == 1 && i == 0)) cout << ans[i];
      if(i > 0) cout << 'x';
      if(i > 1) cout << "^" << i;
    }
  }
  cout << endl;
}

template<class T> ostream& operator << (ostream& ost, vector<T> const& v) { ost << "["; rep(i, v.size()) { if(i) ost << ", "; ost << v[i]; } ost << "]"; return ost; }

int main() {

  while(cin >> N >> M && (N | M)) {
    vector<tuple<int, int, vector<int>>> in;
    rep(i, M) {
      int s, t; cin >> s >> t; s--, t--;
      string poly; cin >> poly; auto r = change_poly(poly);
      in.emplace_back(s, t, r);
    }

    init();

    rep(i, M) {
      add_edge(get<0>(in[i]), get<1>(in[i]), get<2>(in[i]));
      add_edge(get<1>(in[i]), get<0>(in[i]), get<2>(in[i]));
    }

//    add_edge(S, 0, inf_flow);
//    add_edge(N-1, T, inf_flow);
    auto ans = max_flow(0, N-1);

    int all0 = 1;
    rep(i, ans.size()) {
      all0 &= ans[i] == 0;
    }

    if(all0) cout << 0 << endl;
    else output(ans);
  }
  
  return 0;
}