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
//Name: Mobile Network
//Level: 3
//Category: グラフ,Graph,最大流
//Note:

/**
 * x^kの項に対する係数をL-k番目の要素としてもつようなvectorを考え、これを辞書順で最大にすればよい。
 * フローの型がベクトル値である以外は、普通の最大流で求められる。
 * ただし、residual flowがあるかどうかの判定は、0でない最高次の項の正負で判定する。
 *
 * オーダーは O(M^2 NL)。
 */
#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
#include <string>

using namespace std;

typedef vector<int> Poly;
namespace std {
    Poly& operator +=(Poly &a, const Poly &b) {
        for(int i = 0; i < a.size(); ++i) {
            a[i] += b[i];
        }
        return a;
    }
    Poly& operator -=(Poly &a, const Poly &b) {
        for(int i = 0; i < a.size(); ++i) {
            a[i] -= b[i];
        }
        return a;
    }
    Poly operator -(const Poly &a, const Poly &b) {
        Poly res = a;
        res -= b;
        return res;
    }
};

bool is_residual(const Poly &a) {
    for(int v : a) {
        if(v != 0) return v > 0;
    }
    return false;
}

const int L = 50;

template<class Flow>
struct Edge {
    int from, to;
    Flow capacity, flow;
    Edge *back;
    Edge() {}
    Edge(int from, int to, Flow c, Edge *b) : from(from), to(to), capacity(c), flow(Poly(L+1, 0)), back(b) {}
};

template<class Flow>
void make_edge(vector<vector<Edge<Flow>*>> &g, int src, int dst, Flow c) {
    auto *e = new Edge<Flow>(src, dst, c, nullptr);
    auto *back = e->back = new Edge<Flow>(dst, src, c, e);
    g[src].push_back(e);
    g[dst].push_back(back);
}

template <class T>
T dinic_augment(vector<vector<Edge<T>*>> &graph, vector<int> &level, vector<bool> &finished, int u, int sink, T cur)/*{{{*/
{
    if (u == sink || !is_residual(cur)) {
        return cur;
    }
    if (finished[u]) {
        return Poly(L+1, 0);
    }
    finished[u] = true;
    for(auto e : graph[u]) {
        if(e->capacity > e->flow && level[e->to] > level[u]) {
            const T f = dinic_augment(graph, level, finished, e->to, sink, min(cur, e->capacity - e->flow));
            if (is_residual(f)) {
                e->flow += f;
                e->back->flow -= f;
                finished[u] = false;
                return f;
            }
        }
    }
    return Poly(L+1, 0);
}/*}}}*/

// O(V^2 E)
template <typename T>
T dinic(vector<vector<Edge<T>*>> &graph, int source, int sink)/*{{{*/
{
    const int N = graph.size();
    T max_flow(L+1, 0);

    vector<int> level(N);
    vector<bool> finished(N);
    while (true) {
        fill(level.begin(), level.end(), -1);
        level[source] = 0;
        queue<int> q;
        q.push(source);

        int d = N;
        while (!q.empty() && level[q.front()] < d) {
            const int u = q.front();
            q.pop();

            if (u == sink) {
                d = level[u];
            }
            for(auto e : graph[u]) {
                if (level[e->to] < 0 && e->capacity > e->flow) {
                    q.push(e->to);
                    level[e->to] = level[u] + 1;
                }
            }
        }

        fill(finished.begin(), finished.end(), false);
        bool updated = false;
        while (true) {
            const T f = dinic_augment<T>(graph, level, finished, source, sink, Poly(L+1, 100*500*100));
            if (!is_residual(f)) {
                break;
            }
            max_flow += f;
            updated = true;
        }

        if (!updated) {
            break;
        }
    }

    return max_flow;
}/*}}}*/

typedef string::const_iterator Iterator;
int number(Iterator &it) {
    int res = 0;
    while(isdigit(*it)) {
        res *= 10;
        res += *it - '0';
        ++it;
    }
    return res;
}

pair<int,int> term(Iterator &it) {
    pair<int,int> res(1, 0);
    if(isdigit(*it)) res.first = number(it);
    if(*it == 'x') {
        res.second = 1;
        ++it;
        if(*it == '^') {
            ++it;
            res.second = number(it);
        }
    }
    return res;
}

Poly parse(const string &s) {
    Iterator it = s.begin();
    Poly res(L+1, 0);
    do {
        const auto t = term(it);
        res[L-t.second] = t.first;
    } while(*it++ == '+');
    return res;
}

bool solve() {
    int N, M;
    cin >> N >> M;
    if(!N && !M) return false;

    vector<vector<Edge<Poly>*>> g(N);
    for(int i = 0; i < M; ++i) {
        int a, b;
        string expr;
        cin >> a >> b >> expr;
        --a; --b;
        make_edge(g, a, b, parse(expr));
    }
    const auto ans = dinic(g, 0, N-1);
    bool first = true;
    for(int i = 0; i <= L; ++i) {
        if(ans[i] != 0) {
            if(!first) cout << "+";
            if(ans[i] > 1 || i == L) cout << ans[i];
            const int ord = L - i;
            if(ord >= 1) {
                cout << "x";
                if(ord >= 2) {
                    cout << "^" << ord;
                }
            }
            first = false;
        }
    }
    if(first) cout << 0;
    cout << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while(solve()) ;
    return 0;
}