#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;
    }
}


Measured memory_bytes: 3668