#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct capacity {
  vector<int> val;
  capacity():val(55, 0){}
  capacity(vector<int> ini):val(ini){}
  capacity operator + (capacity r) {
    vector<int> res(55);
    for(int i = 0; i < 55; i++) res[i] = val[i] + r.val[i];
    return capacity(res);
  }
  capacity operator - (capacity r) {
    vector<int> res(55);
    for(int i = 0; i < 55; i++) res[i] = val[i] - r.val[i];
    return capacity(res);
  }
  capacity operator * (int k) {
    vector<int> res(55);
    for(int i = 0; i < 55; i++) res[i] = val[i] * k;
    return capacity(res);
  }
  capacity& operator - () {
    for(int i = 0; i < 55; i++) val[i] = -val[i];
    return *this;
  }
  bool operator == (const capacity& r) const {
    return val == r.val;
  }
  bool operator < (const capacity& r) const {
    vector<int> x = val, y = r.val;
    reverse(all(x));
    reverse(all(y));
    return x < y;
  }
  bool operator > (const capacity& r) const {
    vector<int> x = val, y = r.val;
    reverse(all(x));
    reverse(all(y));
    return x > y;
  }
};

const capacity INF = capacity(vector<int>(55, inf));
const capacity ZERO = capacity(vector<int>(55, 0));

struct Dinic {
  struct edge {
    int to, rev;
    capacity cap;
    edge(){}
    edge(int to, capacity cap, int rev)
      :to(to), cap(cap), rev(rev){}
  };
  vector< vector<edge> > graph;
  vector<int> level, iter;
  Dinic(){}
  Dinic(int V):graph(V), level(V), iter(V){}
  void add_edge(int from, int to, capacity cap) {
    graph[from].emplace_back(to, cap, graph[to].size());
    graph[to].emplace_back(from, ZERO, graph[from].size()-1);
  }
  void bfs(int s) {
    fill(all(level), -1);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(que.size()) {
      int v = que.front(); que.pop();
      for(int i = 0; i < graph[v].size(); i++) {
	edge& e = graph[v][i];
	if(e.cap > ZERO && level[e.to] < 0) {
	  level[e.to] = level[v] + 1;
	  que.push(e.to);
	}
      }
    }
  }
  capacity dfs(int v, int t, capacity f) {
    if(v == t) return f;
    for(int& i = iter[v]; i < graph[v].size(); i++) {
      edge& e = graph[v][i];
      if(e.cap > ZERO && level[v] < level[e.to]) {
	capacity d = dfs(e.to, t, min(f, e.cap));
	if(d > ZERO) {
	  e.cap = e.cap - d;
	  graph[e.to][e.rev].cap = graph[e.to][e.rev].cap + d;
	  return d;
	}
      }
    }
    return ZERO;
  }
  capacity max_flow(int s, int t) {
    capacity flow = ZERO;
    while(1) {
      bfs(s);
      if(level[t] < 0) return flow;
      fill(all(iter), 0);
      capacity f; while((f = dfs(s, t, INF)) > ZERO) flow = flow + f;
    }
  }
};

capacity to_cap(string s) {
  vector<char> vec;
  s += '+';
  for(char c : s) {
    if(c == '+') {
      if(vec.back() == 'x') vec.push_back('^'), vec.push_back('1');
      else if(isdigit(vec.back())) {
 	if(vec.size() == 1 || (vec.size() > 1 && vec[vec.size()-2] != '^')) {
 	  vec.push_back('x');
 	  vec.push_back('^');
 	  vec.push_back('0');
 	}
      }
    }
    else if(c == 'x' && (vec.empty() || vec.back() == '+')) vec.push_back('1');
    vec.push_back(c);
  }
  vec.pop_back();
  string t = "";
  for(char c : vec) t += c;
  vector<int> cap(55, 0);
  char buf[1024], a[1024], b[1024];
  strcpy(buf, t.c_str());
  int of = 0;
  while(sscanf(buf + of, "%[^x]x^%[^+]", a, b) != EOF) {
    of += strlen(a) + 2 + strlen(b);
    cap[atoi(b)] = atoi(a);
  }
  return capacity(cap);
}

string to_str(capacity cap) {
  string res = "";
  bool flag = false;
  rep(i, cap.val.size()) {
    if(cap.val[i] != 0) {
      string tmp = (i && cap.val[i] == 1 ? "" : to_string(cap.val[i]));
      if(i > 0) tmp += "x";
      if(i > 1) tmp += "^"+to_string(i);
      if(flag) tmp = tmp + "+";
      res = tmp + res;
      flag = true;
    }
  }
  return (res == "" ? "0" : res);
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, M;
  while(cin >> N >> M, N || M) {
    Dinic graph(N);
    rep(i, M) {
      int u, v;
      string p;
      cin >> u >> v >> p;
      --u, --v;
      capacity c = to_cap(p);
      // rep(j, 4) cout << c.val[j] << " ";
      // cout << endl;
      graph.add_edge(u, v, c);
      graph.add_edge(v, u, c);
    }
    capacity res = graph.max_flow(0, N-1);
    //cout << "rem" << endl;
    // rep(i, graph.graph.size()) {
    //   cout << i << " : " << endl;
    //   rep(j, graph.graph[i].size()) {
    //  	cout << graph.graph[i][j].to << "\\";
    //  	rep(k, 5) cout << graph.graph[i][j].cap.val[k] << " ";
    //  	cout << endl;
    //   }
    //   cout << endl;
    // }
    //cout <<"ans" << endl;
    //rep(j, 4) cout << res.val[j] << " ";
    //cout << endl;
    cout << to_str(res) << endl;
  }

  return 0;
}

Measured memory_bytes: 4232