/*
 * 2328.cc: Mobile Network
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100;
const int L = 50;

const int INF = 1 << 30;

/* typedef */

struct Poly {
  int as[L + 1];
  Poly() { _clear(); }
  Poly(string &s) {
    _clear();
    int pos = 0, sn = s.size();
    while (pos < sn) {
      int ai = _read_int(s, pos);
      int k = 0;
      if (pos < sn && s[pos] == 'x') {
	pos++;
	k = 1;
	if (ai == 0) ai = 1;
	if (pos < sn && s[pos] == '^') {
	  pos++;
	  k = _read_int(s, pos);
	}
      }
      as[k] = ai;
      if (pos < sn && s[pos] == '+') pos++;
    }
  }

  void _clear() { memset(as, 0, sizeof(as)); }

  int _read_int(string &s, int &pos) {
    int num = 0, sn = s.size();
    while (pos < sn && s[pos] >= '0' && s[pos] <= '9')
      num = num * 10 + s[pos++] - '0';
    return num;
  }

  bool operator<(const Poly &p) const {
    for (int i = L; i >= 0; i--)
      if (as[i] != p.as[i]) return (as[i] < p.as[i]);
    return false;
  }
  
  bool operator>(const Poly &p) const { return (p < *this); }

  Poly operator+(const Poly &p) const {
    Poly r;
    for (int i = 0; i <= L; i++) r.as[i] = as[i] + p.as[i];
    return r;
  }

  Poly operator-(const Poly &p) const {
    Poly r;
    for (int i = 0; i <= L; i++) r.as[i] = as[i] - p.as[i];
    return r;
  }

  void print() {
    bool first = true;
    for (int i = L; i >= 0; i--) {
      if (as[i]) {
	if (! first) putchar('+');
	first = false;
	if (i == 0 || as[i] > 1) printf("%d", as[i]);
	if (i) {
	  putchar('x');
	  if (i > 1) printf("^%d", i);
	}
      }
      else if (i == 0 && first) putchar('0');
    }
    putchar('\n');
  }
};

typedef queue<int> qi;
typedef pair<int,Poly> pip;
typedef vector<pip> vpip;

/* global variables */

vpip nbrs[MAX_N];
Poly minfs[MAX_N], flows[MAX_N][MAX_N], pinf, pzero;
int prvs[MAX_N];

/* subroutines */

Poly maxflow(int st, int gl) {
  memset(flows, 0, sizeof(flows));
  Poly max_flow;

  for (;;) {
    //printf("max_flow = %d, limit = %d\n", max_flow, limit);

    memset(prvs, -1, sizeof(prvs));
    prvs[st] = st;
    minfs[st] = pinf;

    qi q;
    q.push(st);

    while (! q.empty()) {
      int ui = q.front(); q.pop();

      if (ui == gl) break;
      vpip& nbru = nbrs[ui];
      for (vpip::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
        int vi = vit->first;
        Poly vc = vit->second - flows[ui][vi];
        if (prvs[vi] < 0 && vc > pzero) {
          prvs[vi] = ui;
          minfs[vi] = (minfs[ui] < vc) ? minfs[ui] : vc;
          q.push(vi);
        }
      }
    }

    if (prvs[gl] < 0) break;

    Poly min_flow = minfs[gl];
    for (int j = gl; j != st;) {
      int i = prvs[j];
      flows[i][j] = flows[i][j] + min_flow;
      flows[j][i] = flows[j][i] - min_flow;
      j = i;
    }

    max_flow = max_flow + min_flow;
  }

  return max_flow;
}

/* main */

int main() {
  pinf.as[L] = INF;

  for (;;) {
    int n, m;
    cin >> n >> m;
    if (n == 0) break;

    for (int i = 0; i < n; i++) nbrs[i].clear();
    
    for (int i = 0; i < m; i++) {
      int ai, bi;
      string ps;
      cin >> ai >> bi >> ps;
      ai--, bi--;
      Poly p(ps);

      nbrs[ai].push_back(pip(bi, p));
      nbrs[bi].push_back(pip(ai, p));
    }

    Poly mf = maxflow(0, n - 1);
    mf.print();
  }
  return 0;
}

Measured memory_bytes: 3380