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;

constexpr int INF = 1e9;
constexpr int MAX_L = 51;

using weight = vector<int>;

vector<int> operator-(vector<int> l, vector<int> const& r) {
    for(int i = 0; i < (int)l.size(); ++i) {
        l[i] -= r[i];
    }
    return l;
}
vector<int> operator+(vector<int> l, vector<int> const& r) {
    for(int i = 0; i < (int)l.size(); ++i) {
        l[i] += r[i];
    }
    return l;
}

struct edge {
    int to;
    weight cap;
    int rev;
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to, weight cap) {
    g[from].push_back(edge{to, cap, static_cast<int>(g[to].size())});
    g[to].push_back(edge{from, vector<int>(MAX_L), static_cast<int>(g[from].size()-1)});
}

void bfs(graph& g, std::vector<int>& level, int s) {
    for(int i=0; i<level.size(); ++i) {
        level[i] = -1;
    }
    level[s] = 0;
    std::queue<int> que;
    que.push(s);
    while(!que.empty()) {
        int v = que.front(); que.pop();
        for(int i = 0; i < (int)g[v].size(); ++i) {
            edge& e = g[v][i];
            if(e.cap > vector<int>(MAX_L) && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

weight dfs(graph& g, std::vector<int>& level, std::vector<int>& iter, int v, int t, weight f) {
    if(v == t) {
        return f;
    }
    vector<int> const zero(MAX_L);
    for(int& i = iter[v]; i < g[v].size(); ++i) {
        edge& e = g[v][i];
        if(e.cap > zero && level[v] < level[e.to]) {
            weight d = dfs(g, level, iter, e.to, t, std::min(f, e.cap));
            if(d > zero) {
                e.cap = e.cap - d;
                g[e.to][e.rev].cap = g[e.to][e.rev].cap + d;
                return d;
            }
        }
    }
    return zero;
}

weight max_flow(graph& g, int s, int t) {
    vector<int> zero(MAX_L);
    vector<int> inf(MAX_L, INF);
    weight flow = zero;
    std::vector<int> level(g.size(), -1);
    std::vector<int> iter(g.size(), 0);
    while(true) {
        bfs(g, level, s);
        if(level[t] < 0) {
            return flow;
        }
        for(int i = 0; i < iter.size(); ++i) {
            iter[i] = 0;
        }
        weight f;
        while((f = dfs(g, level, iter, s, t, inf)) > zero) {
            flow = flow + f;
        }
    }
}

int number(string const& s, int& p) {
    int res = 0;
    while(isdigit(s[p])) {
        res *= 10;
        res += s[p++] - '0';
    }
    return res;
}

pair<int, int> term(string const& s, int& p) {
    int a = number(s, p);
    if(a == 0) {
        a = 1;
    }
    int l = 0;
    if(p < s.size()) {
        if(p + 1 < s.size() && s[p + 1] == '^') {
            p += 2;
            l = number(s, p);
        } else {
            l = 1;
            p++;
        }
    }
    return make_pair(a, l);
}

vector<int> parse(string const& s) {
    int p = 0;
    vector<int> res(MAX_L);
    while(p < s.size()) {
        auto t = term(s, p);
        res[t.second] = t.first;
        p++; // +
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int N, M;
    while(cin >> N >> M, N) {
        graph g(N);
        int const source = 0, sink = N - 1;
        for(int i = 0; i < M; ++i) {
            int u, v;
            string p;
            cin >> u >> v >> p;
            auto cap = parse(p);
            add_edge(g, u - 1, v - 1, cap);
            add_edge(g, v - 1, u - 1, cap);
        }
        auto flow = max_flow(g, source, sink);
        string res;
        for(int i = 0; i < MAX_L; ++i) {
            if(flow[i] != 0) {
                if(res.size() != 0) {
                    res += '+';
                }
                if(i == MAX_L - 1 || flow[i] != 1) {
                    res += to_string(flow[i]);
                }
                if(MAX_L - 1 - i >= 1) {
                    res += 'x';
                }
                if(MAX_L - 1 - i > 1) {
                    res += "^" + to_string(MAX_L - 1 - i);
                }
            }
        }
        if(res.empty()) {
            res = "0";
        }
        cout << res << endl;
    }
}
