#include <array>
#include <cctype>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct weight {
	static constexpr int MAX_L = 50;
	typedef array<int, MAX_L + 1> A;

	A coefficients;

	inline static int number(string::const_iterator &it) {
		int res = 0;
		while(isdigit(*it)) {
			res = res * 10 + *it - '0';
			++it;
		}
		return res;
	}

	inline void parse(string::const_iterator &it) {
		const int c = (isdigit(*it) ? number(it) : 1);

		if(*it != 'x') {
			coefficients.back() = c;
			return;
		}

		++it;

		int e = 1;
		if(*it == '^') {
			++it;
			e = number(it);
		}

		coefficients[MAX_L - e] = c;
	}

	weight(const string &s = "0") {
		coefficients.fill(0);

		string::const_iterator it = s.cbegin();
		parse(it);
		while(*it == '+') {
			++it;
			parse(it);
		}
	}

	weight(const A &a):coefficients(a) {}
	weight(const weight &w):coefficients(w.coefficients) {}

	inline bool operator<(const weight &w) const {
		return coefficients < w.coefficients;
	}


	inline weight &operator+=(const weight &w) {
		for(unsigned i = 0; i < coefficients.size(); ++i) {
			coefficients[i] += w.coefficients[i];
		}
		return *this;
	}

	inline weight &operator-=(const weight &w) {
		for(unsigned i = 0; i < coefficients.size(); ++i) {
			coefficients[i] -= w.coefficients[i];
		}
		return *this;
	}

	inline string to_string() const {
		string res;
		for(unsigned i = 0; i < coefficients.size(); ++i) {
			if(coefficients[i] != 0) {
				if(res.size()) res += '+';

				const int e = MAX_L - i;

				if(e == 0 || coefficients[i] > 1) {
					res += std::to_string(coefficients[i]);
				}

				if(e >= 1) {
					res += 'x';
					if(e >= 2) res += "^" + std::to_string(e);
				}
			}
		}
		if(res == "") res = "0";
		return res;
	}
};

struct edge {
	int to;
	weight cap;
	int rev;
	edge(int to_, weight cap_, int rev_):to(to_), cap(cap_), rev(rev_){}
};

const weight INF("1000x^50");
const weight ZERO;

vector<vector<edge> > G;
vector<int> level;
vector<int> iter;

void init(int V) {
	G.assign(V, vector<edge>());
	level.resize(V);
	iter.resize(V);
}

void add_edge(int from, int to, weight cap) {
	G[from].emplace_back(to, cap, G[to].size());
	G[to].emplace_back(from, cap, G[from].size() - 1);
}

void bfs(int s) {
	fill(level.begin(), level.end(), -1);
	queue<int> que;
	level[s] = 0;
	que.push(s);

	while(!que.empty()) {
		const int v = que.front();
		que.pop();

		for(const auto &e : G[v]) {
			if(ZERO < e.cap && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}

weight dfs(int v, int t, weight f) {
	if(v == t) return f;

	for(int &i = iter[v]; i < static_cast<int>(G[v].size()); ++i) {
		edge &e = G[v][i];
		if(ZERO < e.cap && level[v] < level[e.to]) {
			const weight d = dfs(e.to, t, min(f, e.cap));
			if(ZERO < d) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}

	return ZERO;
}

weight max_flow(int s, int t) {
	weight flow = ZERO;

	for(;;) {
		bfs(s);
		if(level[t] < 0) return flow;

		fill(iter.begin(), iter.end(), 0);
		for(weight f; ZERO < (f = dfs(s, t, INF)); flow += f);
	}
}


int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	for(int n, m; cin >> n >> m && n;) {
		init(n);

		for(int i = 0; i < m; ++i) {
			int a, b;
			string p;
			cin >> a >> b >> p;
			add_edge(a - 1, b - 1, weight(p));
		}

		cout << max_flow(0, n - 1).to_string() << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1568