// AOJ 2328 Mobile Network
// 2018.3.13 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define INF      0x01010101
#define CZ       0
#define CINF     1

#define VMAX 53
typedef struct { int to; short cap; int rev; } EDGE;
EDGE edge[VMAX][VMAX]; int hi[VMAX];
int V;				// 頂点数
int level[VMAX], iter[VMAX];
int queue[2*VMAX], qtop;

typedef struct { char w; short c[55]; } CAP;
CAP cap[15000]; int cid;

char buf[600], *p;
int in()
{
	int n = 0;
	while (isdigit(*p)) n = 10*n + (*p++ & 0xf);
	p++;
	return n;
}

int cap_new() { int id = cid++;	cap[id].w = 1, cap[id].c[0] = 0; return id; }
void cap_set(int id1, int id2) { memcpy(cap+id1, cap+id2, sizeof(CAP)); }

void cap_norm(int id)
{
	int w = cap[id].w - 1;
	while (w > 0 && cap[id].c[w] == 0) w--;
	cap[id].w = w + 1;
}

int cap_zero(int id) { return cap[id].c[cap[id].w-1]; }

int cap_cmp(int id1, int id2)
{
	int i, w1 = cap[id1].w-1, w2 = cap[id2].w-1;
	if (w1 > w2) return  cap[id1].c[w1];
	if (w2 > w1) return  -cap[id2].c[w2];
	for (i = w1; i >= 0; i--) {
		if (cap[id1].c[i] != cap[id2].c[i]) return cap[id1].c[i] - cap[id2].c[i];
	}
	return 0;
}

void cap_add(int id1, int id2)
{
	int i, w1 = cap[id1].w, w2 = cap[id2].w;
	if (w1 > w2) {
		for (i = 0; i < w2; i++) cap[id1].c[i] += cap[id2].c[i];
	} else {
		for (i = 0; i < w1; i++) cap[id1].c[i] += cap[id2].c[i];
		for (     ; i < w2; i++) cap[id1].c[i]  = cap[id2].c[i];
		cap[id1].w = cap[id2].w;
		cap_norm(id1);
	}
}

void cap_sub(int id1, int id2)
{
	int i, w1 = cap[id1].w, w2 = cap[id2].w;
	if (w1 > w2) {
		for (i = 0; i < w2; i++) cap[id1].c[i] -= cap[id2].c[i];
	} else {
		for (i = 0; i < w1; i++) cap[id1].c[i] -= cap[id2].c[i];
		for (     ; i < w2; i++) cap[id1].c[i] = -cap[id2].c[i];
		cap[id1].w = cap[id2].w;
		cap_norm(id1);
	}
}

void str2cap(int id)
{
	int c, e, w = 0;

	while (*p > ' ') {
		if (*p == '+') p++;
		c = 1; if (isdigit(*p)) c = in(), p--;
		e = 0; if (*p == 'x') {
			p++; e = 1;
			if (*p == '^') { p++; if (isdigit(*p)) e = in(), p--; }
		}
		cap[id].c[e] = c;
		if (e > w) w = e;
	}
	cap[id].w = w+1;
}

void coutcap(int id)
{
	int f = 0, i, w = cap[id].w-1;

	for (i = w; i > 0; i--) {
		if (cap[id].c[i] == 0) continue;
		if (f) putchar('+');
		if (cap[id].c[i] != 1) printf("%d", cap[id].c[i]);
		putchar('x'); f = 1;
		if (i > 1) printf("^%d", i);
	}
	if (!f) printf("%d", cap[id].c[0]);
	else if (cap[id].c[0]) printf("+%d", cap[id].c[0]);
	putchar('\n');
}

void add_edge(int from, int to, int id)
{
	int f, t, c;
	EDGE *e;

	f = hi[from]++, t = hi[to]++;
	e = &edge[from][f], e->to = to, e->cap = id, e->rev = t;
	c = cap_new(), cap_set(c, id);
	e = &edge[to][t], e->to = from, e->cap = c, e->rev = f;
}

void bfs(int s)
{
	int i, v;
	EDGE *e;
	
	memset(level, -1, V << 2);
	level[s] = 0;
	queue[0] = s, qtop =1;
	while (qtop) {
		v = queue[--qtop];
		for (i = 0; i < hi[v]; i++) {
			e = &edge[v][i];
			if (cap_zero(e->cap) > 0 && level[e->to] < 0) {
				level[e->to] = level[v] + 1;
				queue[qtop++] = e->to;
			}
		}
	}
}
 
int dfs(int v, int t, int f)
{
	int *i, d, ff;
	EDGE *e;
	
	ff = cap_new(); cap_set(ff, f);
	if (v == t) return ff;
	d = cap_new();
	for (i = &iter[v]; *i < hi[v]; (*i)++) {
		e = &edge[v][*i];
		if (cap_zero(e->cap) > 0 && level[v] < level[e->to]) {
			if (cap_cmp(ff, e->cap) <= 0) cap_set(d, dfs(e->to, t, ff));
			else                          cap_set(d, dfs(e->to, t, e->cap));
			if (cap_zero(d) > 0) {
				cap_sub(e->cap, d);
				cap_add(edge[e->to][e->rev].cap, d);
				return d;
			}
		}
	}
	return CZ;
}
 
int maxFlow(int s, int t)
{
	int f =	cap_new();
	int flow = cap_new();

	while (1) {
		bfs(s);
		if (level[t] < 0) break;
		memset(iter, 0, V << 2);
		while (1) {
			cap_set(f, dfs(s, t, CINF));
			if (cap_zero(f) <= 0) break;
			cap_add(flow, f);
		}
	}
	return flow;
}

int main()
{
	int N, M, i, u, v;

	while (fgets(p=buf, 10, stdin) && *p != '0') {
		memset(cap, 0, sizeof(cap));
		cap[CZ].w = 1, cap[CZ].c[0] = 0;
		cap[CINF].w = 53, cap[CINF].c[52] = 1;
		cid = 2;

		N = in(), M = in();
		V = N; memset(hi, 0, V << 2);

		for (i = 0; i < M; i++) {
			fgets(p=buf, 600, stdin);
			u = in()-1, v = in()-1;
			str2cap(cid++);
			add_edge(u, v, cid-1);
		}
		coutcap(maxFlow(0, N-1));
	}
	return 0;
}


Measured memory_bytes: 3400