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 <cstdio>
#include <cstdint>
#include <cassert>
#include <cctype>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stdexcept>
#include <iostream>
#include <functional>
#include <queue>

class polynomial;
static const std::vector<std::string> ops={"+-", "*/%", "^"};
// operator % を定義していると多項式の GCD とかも簡単に書けるんですよね
// べき乗の演算子はふつう右結合のはずなんですが，そういう入力はこないと
// 思うので，左結合で書いてしまいます．

polynomial parse(const std::string&, size_t&, size_t);

std::string normalize(const std::string& s) {
  std::string res;
  enum { NONE, PAREN, FACTOR, OPERATOR } last = NONE;
  for (size_t i=0; i<s.length(); ++i) {
    if (s[i] == '(') {
      if (last == FACTOR) res += '*';
      res += '(';
      last = PAREN;
    } else if (s[i] == ')') {
      res += ')';
      last = FACTOR;
    } else if (isalnum(s[i])) {
      if (last == FACTOR) res += '*';
      res += s[i];
      if (isdigit(s[i])) {
        while (isdigit(s[i+1]))
          res += s[++i];
      }
      last = FACTOR;
    } else if (!isspace(s[i])) {
      res += s[i];
      last = OPERATOR;
    }
  }
  return res;
}

class polynomial {
  using deg_type = int;
  using coef_type = intmax_t;
  // e.g., polynomial("2x^2+1") => cs: {"xx": 2, "": 1}
  // 冷静に考えると，polynomial("x^100000") でつらくなりますね
  // {("x", 2): 2, ("", 0): 1} みたいにするべき？
  // そうした方がいい気がするのでそのうちします
  // と思ったけど ab みたいなのをどう扱いますか？ やめます．
  // やっぱりやめません．
  // というか文字を決めうちでいいなら上の式も {2: 2, 0: 1} でいいですね
  std::map<deg_type, coef_type> cs;

  polynomial& normalized() {
    for (auto it=cs.begin(); it!=cs.end();) {
      if (it->second == 0) {
        it = cs.erase(it);
      } else {
        ++it;
      }
    }
    return *this;
  }

public:
  /* constructors */
  polynomial(const std::string& s) {
    std::string t = normalize(s);
    size_t i = 0;
    polynomial tmp = parse(t, i, 0);
    cs = std::move(tmp.cs);
  }

  polynomial(deg_type d, coef_type c) {
    cs[d] = c;
  }

  polynomial(coef_type c) {
    cs[0] = c;
  }

  polynomial() {}

  /* binary operations (@=) */
  polynomial& operator +=(const polynomial& rhs) {
    for (const auto& p: rhs.cs) cs[p.first] += p.second;

    // Poly("+x") + Poly("-x") の結果 Poly("0") になりますが，このとき
    // cs は {"": 0} になるべきで {"x": 0} になるべきではありません
    return normalized();
  }

  polynomial& operator -=(const polynomial& rhs) {
    for (const auto& p: rhs.cs) cs[p.first] -= p.second;
    return normalized();
  }

  polynomial& operator *=(const polynomial& rhs) {
    // Note: this と *rhs が identical でもつらくならない必要がある
    std::map<deg_type, coef_type> tmp;
    for (const auto& p1: cs)
      for (const auto& p2: rhs.cs) {
        deg_type param = p1.first+p2.first;
        tmp[param] += p1.second * p2.second;
      }
    cs = std::move(tmp);
    return normalized();
  }

  // not implemented
  polynomial& operator /=(const polynomial& rhs);  
  polynomial& operator %=(const polynomial& rhs);  

  polynomial& operator ^=(const polynomial& rhs) {
    if (!(rhs.cs.size() == 1 && rhs.cs.begin()->first == 0))
      throw std::logic_error("y should be constant in x^y");

    int iexp = rhs.cs.at(0);
    if (iexp < 0)
      throw std::logic_error("y should be non-negative in x^y");

    polynomial dbl(*this);
    cs.clear();
    cs[0] = 1;
    for (; iexp; iexp>>=1) {
      if (iexp & 1) (*this) *= dbl;
      dbl *= dbl;
    }
    return normalized();
  }

  // wrapper
  polynomial& op_eq(char op, const polynomial& rhs) {
    switch (op) {
    case '+': return (*this) += rhs;
    case '-': return (*this) -= rhs;
    case '*': return (*this) *= rhs;
    // case '/': return (*this) /= rhs;
    // case '%': return (*this) %= rhs;
    case '^': return (*this) ^= rhs;
    default: assert(false);
    }
  }

  /* binary opeartions (@) */
  polynomial operator +(const polynomial& other) const { return polynomial(*this) += other; }
  polynomial operator -(const polynomial& other) const { return polynomial(*this) -= other; }
  polynomial operator *(const polynomial& other) const { return polynomial(*this) *= other; }
  // polynomial operator %(const polynomial& other) const { return polynomial(*this) %= other; }
  // polynomial operator /(const polynomial& other) const { return polynomial(*this) /= other; }
  polynomial operator ^(const polynomial& other) const { return polynomial(*this) ^= other; }

  /* binary opeartions (relations) */
  bool operator <(const polynomial& rhs) const {
    polynomial tmp(*this);
    tmp -= rhs;
    // lhs-rhs < 0 <=> lhs < rhs
    // で，最高次的なやつのの符号で決めます
    if (tmp.cs.empty()) return false;
    return std::prev(tmp.cs.end())->second < 0;
  }

  bool operator ==(const polynomial& rhs) const {
    return cs == rhs.cs;
  }

  operator std::string() const {
    std::string res;
    for (auto it=cs.rbegin(); it!=cs.rend(); ++it) {
      deg_type d = it->first;
      coef_type c = it->second;
      if (c == 0) continue;
      if (c > 0) {
        if (!res.empty()) res += '+';
      } else {
        res += '-';
        c = -c;
      }
      if (c > 1 || d == 0) res += std::to_string(c);
      if (d > 0) {
        res += 'x';
        if (d > 1) {
          res += '^';
          res += std::to_string(d);
        }
      }
    }
    if (res.empty()) res = "0";
    return res;
  }
};

polynomial parse(const std::string& s, size_t& i, size_t preced) {
  if (preced == ops.size()) {
    if (s[i] == '(') {
      polynomial res = parse(s, ++i, 0);
      assert(s[i] == ')');
      ++i;
      return res;
    }
    if (isalpha(s[i])) {
      assert(s[i] == 'x');
      ++i;
      return polynomial(1, 1);
    }
    if (isdigit(s[i])) {
      intmax_t res = s[i]-'0';
      while (++i < s.length() && isdigit(s[i]))
        res = res*10+s[i]-'0';
      return polynomial(0, res);
    }
    assert(false);
  }

  polynomial res = parse(s, i, preced+1);
  while (i < s.length()) {
    char op = s[i];
    if (!std::count(ops[preced].begin(), ops[preced].end(), op)) break;
    polynomial tmp = parse(s, ++i, preced+1);
    res.op_eq(op, tmp);
  }
  return res;
}

template <class Tp>
Tp inf() { return Tp(); }
template <>
polynomial inf() { return polynomial(100, 1); }

template <class Tp>
struct Edge {
  size_t src, dst;
  Tp cap;
  size_t rev;
  Edge(size_t src, size_t dst, Tp cap, size_t rev):
    src(src), dst(dst), cap(cap), rev(rev)
  {}
};

template <class Tp>
struct graph: public std::vector<std::vector<Edge<Tp>>> {
  graph(size_t n): std::vector<std::vector<Edge<Tp>>>(n) {}

  void connect_with(size_t src, size_t dst, Tp cap) {
    (*this)[src].emplace_back(src, dst, cap, (*this)[dst].size());
    (*this)[dst].emplace_back(dst, src, cap, (*this)[src].size()-1);
  }
};

template <class Tp>
std::vector<int> distance(graph<Tp>& g, size_t s) {
  std::vector<int> cost(g.size(), -1);
  std::queue<size_t> q;
  cost[s] = 0;
  q.emplace(s);
  while (!q.empty()) {
    size_t v = q.front();
    q.pop();
    for (const auto& e: g[v]) {
      if (Tp(0) < e.cap && cost[e.dst] < 0) {
        cost[e.dst] = cost[v] + 1;
        q.push(e.dst);
      }
    }
  }
  return cost;
}

template <class Tp>
Tp max_flow(graph<Tp>& g, size_t s, size_t t) {
  Tp flow = Tp(0);
  std::vector<size_t> iter;
  std::vector<int> cost;

  std::function<Tp (size_t, Tp)> augment=[&](size_t v, Tp f)->Tp {
    if (v == t) return f;
    for (size_t& i=iter[v]; i<g[v].size(); ++i) {
      Edge<Tp>& e = g[v][i];
      if (Tp(0) < e.cap && cost[v] < cost[e.dst]) {
        Tp d = augment(e.dst, std::min(f, e.cap));
        if (Tp(0) < d) {
          e.cap -= d;
          g[e.dst][e.rev].cap += d;
          return d;
        }
      }
    }
    return Tp(0);
  };

  while (true) {
    cost = distance(g, s);
    if (cost[t] < 0) return flow;
    iter.assign(g.size(), 0);
    Tp f;
    while (Tp(0) < (f = augment(s, inf<Tp>())))
      flow += f;
  }
}

int testcase_ends() {
  size_t N, M;
  scanf("%zu %zu", &N, &M);

  if (N == 0 && M == 0) return 1;

  graph<polynomial> g(N);
  for (size_t i=0; i<M; ++i) {
    size_t src, dst;
    scanf("%zu %zu", &src, &dst);
    --src;
    --dst;

    char buf[1024];
    scanf("%s", buf);
    std::string s = buf;

    polynomial p(s);
    g.connect_with(src, dst, p);
  }

  printf("%s\n", std::string(max_flow(g, 0, N-1)).c_str());
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}

