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

Measured memory_bytes: 3660