Language: C++

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
//const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

typedef vi Poly;

const Poly ZERO(51, 0);
const Poly INF(51, 1e8);

Poly operator-(const Poly& a, const Poly b)
{
	Poly res(51);
	REP(i, 51) res[i] = a[i] - b[i];
	return res;
}

Poly operator+(const Poly& a, const Poly b)
{
	Poly res(51);
	REP(i, 51) res[i] = a[i] + b[i];
	return res;
}

bool operator<(const Poly& a, const Poly& b)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == b[i]) continue;
		return a[i] < b[i];
	}
	return false;
}

bool operator<=(const Poly& a, const Poly& b)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == b[i]) continue;
		return a[i] < b[i];
	}
	return true;
}

bool operator>(const Poly& a, const Poly& b)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == b[i]) continue;
		return a[i] > b[i];
	}
	return false;
}

Poly min(const Poly& a, const Poly& b)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == b[i]) continue;
		if (a[i] < b[i]) return a;
		else return b;
	}
	return b;
}

bool resid(const Poly& a)
{
	for (int i = 50; i >= 0; i--)
	{
		if (a[i] == 0) continue;
		return a[i] > 0;
	}
	return false;
}

template <typename Flow>
struct FEdge {
	int from, to;
	Flow cap; int rev;
	FEdge(int s, int t, Flow f, int r) : from(s), to(t), cap(f), rev(r) {}
};

template<typename Flow> using FGraph = vector<vector<FEdge<Flow>>>;

template <typename Flow>
void add_edge(FGraph<Flow> &g, int from, int to, Flow cap) {
	g[from].emplace_back(from, to, cap, (int)g[to].size());
	g[to].emplace_back(to, from, 0, (int)g[from].size() - 1);
}

template <typename Flow>
Flow augment(FGraph<Flow> &g, vi &d, vector<int> &iter, int v, int t, const Flow &f) 
{
	if (v == t || !resid(f)) return f;
	for (int &i = iter[v]; i < (int)g[v].size(); i++) {
		auto &e = g[v][i];
		if (e.cap > ZERO && d[v] < d[e.to]) {
			Flow ff = augment(g, d, iter, e.to, t, min(f, e.cap));
			if (resid(f)) {
				e.cap = e.cap - ff;
				g[e.to][e.rev].cap = g[e.to][e.rev].cap + ff;
				return ff;
			}
		}
	}
	return ZERO;
}

template <typename Flow>
Flow max_flow(FGraph<Flow> &g, int s, int t, Flow zero = ZERO) {
	int V = g.size();
	Flow flow = zero;
	for (;;) {
		vi d(V, -1);
		queue<int> que;
		d[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (const auto &e : g[v]) {
				if (e.cap <= zero ||  d[e.to] >= 0) continue;
				d[e.to] = d[v] + 1;
				que.push(e.to);
			}
		}
		if (d[t] < 0) return flow;
		vector<int> iter(V, 0);
		Flow f;
		while ((f = augment(g, d, iter, s, t, INF)) > ZERO) flow = flow + f;
	}
}


int num(const string& s, int& p)
{
	assert(isdigit(s[p]));
	int res = 0;
	while (isdigit(s[p]))
	{
		res *= 10;
		res += s[p] - '0';
		p++;
	}
	return res;
}

Poly parse(const string& s)
{
	Poly res(51);
	int n = s.size();
	int p = 0;
	while (p < n)
	{
		int c = 1;
		if (isdigit(s[p]))
		{
			c = num(s, p);
		}
		if (s[p] == 'x')
		{
			p++;
			if (s[p] == '^')
			{
				p++;
				int m = num(s, p);
				res[m] = c;
				p++;
				continue;
			}
			else
			{
				res[1] = c;
				p++;
				continue;
			}
		}
		else
		{
			assert(p == n);
			res[0] = c;
		}
	}
	return res;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, m;
	while (cin >> n >> m, n)
	{
		FGraph<Poly> g(n);
		REP(i, m)
		{
			int a, b; cin >> a >> b; a--; b--;
			string s; cin >> s;
			Poly t = parse(s);
			add_edge(g, a, b, t);
			add_edge(g, b, a, t);
		}
		Poly ans = max_flow(g, 0, n - 1);
		string anss;
		for (int i = 50; i >= 0; i--)
		{
			if (ans[i] > 0)
			{
				if (i > 1)
				{
					if (ans[i] > 1)
					{
						anss += to_string(ans[i]) + "x^" + to_string(i) + "+";
					}
					else
					{
						anss += "x^" + to_string(i) + "+";
					}
				}
				else if (i == 1)
				{
					if (ans[i] > 1)
					{
						anss += to_string(ans[i]) + "x+";
					}
					else
					{
						anss += "x+";
					}
				}
				else if (i == 0)
				{
					anss += to_string(ans[i]) + "+";
				}
			}
		}
		if (anss.size() > 0)
		{
			anss.pop_back();
			cout << anss << endl;
		}
		else cout << 0 << endl;
	}
	return 0;
}

Compiler output:
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/c++allocator.h:33,
                 from /usr/include/c++/14/bits/allocator.h:46,
                 from /usr/include/c++/14/string:43,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/new_allocator.h: In instantiation of 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = FEdge<std::vector<int> >; _Args = {int&, int&, int, int}; _Tp = FEdge<std::vector<int> >]':
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = FEdge<std::vector<int> >; _Args = {int&, int&, int, int}; _Tp = FEdge<std::vector<int> >; allocator_type = std::allocator<FEdge<std::vector<int> > >]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/vector.tcc:117:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&, int&, int, int}; _Tp = FEdge<std::vector<int> >; _Alloc = std::allocator<FEdge<std::vector<int> > >; reference = FEdge<std::vector<int> >&]'
  117 |             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  118 |                                      std::forward<_Args>(__args)...);
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:102:20:   required from 'void add_edge(FGraph<Flow>&, int, int, Flow) [with Flow = std::vector<int>; FGraph<Flow> = std::vector<std::vector<FEdge<std::vector<int> >, std::allocator<FEdge<std::vector<int> > > >, std::allocator<std::vector<FEdge<std::vector<int> >, std::allocator<FEdge<std::vector<int> > > > > >]'
  102 |         g[to].emplace_back(to, from, 0, (int)g[from].size() - 1);
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:212:12:   required from here
  212 |                         add_edge(g, a, b, t);
      |                         ~~~~~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/new_allocator.h:191:11: error: no matching function for call to 'FEdge<std::vector<int> >::FEdge(int&, int&, int, int)'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:94:9: note: candidate: 'FEdge<Flow>::FEdge(int, int, Flow, int) [with Flow = std::vector<int>]'
   94 |         FEdge(int s, int t, Flow f, int r) : from(s), to(t), cap(f), rev(r) {}
      |         ^~~~~
a.cc:94:34: note:   no known conversion for argument 3 from 'int' to 'std::vector<int>'
   94 |         FEdge(int s, int t, Flow f, int r) : from(s), to(t), cap(f), rev(r) {}
      |                             ~~~~~^
a.cc:91:8: note: candidate: 'FEdge<std::vector<int> >::FEdge(const FEdge<std::vector<int> >&)'
   91 | struct FEdge {
      |        ^~~~~
a.cc:91:8: note:   candidate expects 1 argument, 4 provided
a.cc:91:8: note: candidate: 'FEdge<std::vector<int> >::FEdge(FEdge<std::vector<int> >&&)'
a.cc:91:8: note:   candidate expects 1 argument, 4 provided