#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 110
#define MAX_DEGREE 50

//辺を表す構造体(行先、容量、逆辺のインデックス)
struct Edge{
	Edge(int arg_to,vector<int> arg_capacity,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		rev_index = arg_rev_index;
	}
	int to,rev_index;
	vector<int> capacity;
};

int V,E;
int max_degree;

vector<Edge> G[NUM]; //グラフの隣接リスト表現
int dist[NUM]; //sourceからの距離
int cheked_index[NUM]; //どこまで調べ終わったか

//fromからtoへ向かう容量capacityの辺をグラフに追加する
void add_edge(int from,int to,vector<int> capacity){

	vector<int> ZERO;
	for(int i = 0; i <= MAX_DEGREE; i++)ZERO.push_back(0);

	G[from].push_back(Edge(to,capacity,G[to].size()));
	G[to].push_back(Edge(from,ZERO,G[from].size()-1)); //逆辺の、初期容量は0
}

vector<int> get_smaller(vector<int> A,vector<int> B){

	for(int i = max_degree; i >= 0; i--){
		if(A[i] != B[i]){
			if(A[i] > B[i]){ //最高次数が小さい方を採用
				return B;
			}else{
				return A;
			}
		}
	}
	return A;
}


bool is_zero(vector<int> add){
	for(int i = 0; i <= max_degree; i++){
		if(add[i] != 0){
			return false;
		}
	}
	return true;
}

//sourceからの最短距離をBFSで計算する
void bfs(int source){
	for(int i = 0; i < V; i++)dist[i] = -1;
	queue<int> Q;
	dist[source] = 0;
	Q.push(source);

	while(!Q.empty()){
		int node_id = Q.front();
		Q.pop();
		for(int i = 0; i < G[node_id].size(); i++){
			Edge &e = G[node_id][i];
			if(is_zero(e.capacity) == false && dist[e.to] < 0){ //辺の容量が正で、かつエッジの行先に未訪問の場合
				dist[e.to] = dist[node_id]+1;
				Q.push(e.to);
			}
		}
	}
}

//増加パスをDFSで探す
vector<int> dfs(int node_id,int sink,vector<int> tmp_min){

	if(node_id == sink)return tmp_min; //終点についたらtmp_min[★最小の容量★]をreturn

	vector<int> ret;

	for(int &i = cheked_index[node_id]; i < G[node_id].size(); i++){ //node_idから出ているエッジを調査

		Edge &e = G[node_id][i];

		if(is_zero(e.capacity) == false && dist[node_id] < dist[e.to]){ //流せる余裕があり、かつsourceからの距離が増加する方法である場合

			ret = dfs(e.to,sink,get_smaller(tmp_min,e.capacity)); //流せるだけ流す

			if(!is_zero(ret)){ //流せた場合
				for(int k = 0; k <= max_degree; k++){
					e.capacity[k] -= ret[k]; //流した分、エッジの容量を削減する
					G[e.to][e.rev_index].capacity[k] += ret[k]; //逆辺の容量を、流した分だけ増加させる
				}
				return ret;
			}
		}
	}
	//★★エッジのused状況により、for文の内部に到達しない場合あり★★
	if(ret.size() == 0){
		for(int i = 0; i <= max_degree; i++)ret.push_back(0);
	}

	return ret;
}

//sourceからsinkへの最大流を求める
vector<int> max_flow(int source,int sink){ //source:始点 sink:終点

	vector<int> ret,add,tmp_min;
	for(int i = 0; i <= max_degree; i++)ret.push_back(0);

	while(true){ //増加パスが存在する限り、流量を追加し続ける
		bfs(source);
		if(dist[sink] < 0)break; //sourceからsinkへと辿り着く残余グラフがない、つまり増加パスが無くなった場合、break
		for(int i = 0; i < V; i++)cheked_index[i] = 0;

		tmp_min.clear();
		for(int i = 0; i <= max_degree; i++)tmp_min.push_back(BIG_NUM);

		while(!is_zero(add = dfs(source,sink,tmp_min))){ //増加パスが見つかる間、加算
			for(int i = 0; i <= max_degree; i++){
				ret[i] += add[i];
			}
		}
	}

	return ret;
}

bool is_number(char ch){
	return ch >= '0' && ch <= '9';
}

void func(){

	for(int i = 0; i < NUM; i++)G[i].clear();

	int from,to,index,tmp,tmp_degree;
	char buf[1000];
	vector<int> input;

	max_degree = 0;

	for(int loop = 0; loop < E; loop++){

		input.clear();
		for(int i = 0; i <= MAX_DEGREE; i++)input.push_back(0);

		scanf("%d %d %s",&from,&to,buf);
		from--;
		to--;

		index = 0;

		while(buf[index] != '\0'){

			if(is_number(buf[index])){ //係数の場合

				tmp = 0;
				while(is_number(buf[index])){
					tmp = 10*tmp+buf[index]-'0';
					index++;
				}
				if(buf[index] == 'x'){

					index++;

				}else{ //★定数の場合:最後の項であるはず★

					input[0] = tmp;
					break;
				}

			}else if(buf[index] == 'x'){
				tmp = 1;
				index++;
			}

			if(buf[index] == '^'){ //ここに来るまでに係数が設定されているはず

				tmp_degree = 0;
				index++;
				while(is_number(buf[index])){
					tmp_degree = 10*tmp_degree+buf[index]-'0';
					index++;
				}

			}else{ //xの一次項
				tmp_degree = 1;
			}
			input[tmp_degree] = tmp;
			max_degree = max(max_degree,tmp_degree);
			if(buf[index] == '+')index++;
		}

		add_edge(from,to,input);
		add_edge(to,from,input);
	}

	vector<int> ans = max_flow(0,V-1);

	bool is_First = true;

	for(int i = max_degree; i >= 0; i--){
		if(ans[i] == 0)continue;

		if(is_First){
			is_First = false;
		}else{
			printf("+");
		}
		if(ans[i] > 1 || i == 0){
			printf("%d",ans[i]);
		}
		if(i > 0){
			printf("x");
			if(i > 1){
				printf("^%d",i);
			}
		}
	}
	if(is_First){
		printf("0");
	}

	printf("\n");
}

int main(){

	while(true){
		scanf("%d %d",&V,&E);
		if(V == 0 && E == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 3452