The trafic on the Internet is increasing these days due to smartphones. The wireless carriers have to enhance their network infrastructure.

The network of a wireless carrier consists of a number of base stations and lines. Each line connects two base stations bi-directionally. The bandwidth of a line increases every year and is given by a polynomial f(x) of the year x.

Your task is, given the network structure, to write a program to calculate the maximal bandwidth between the 1-st and N-th base stations as a polynomial of x.



Input

The input consists of multiple datasets. Each dataset has the following format:

N M
u1 v1 p1
...
uM vM pM


The first line of each dataset contains two integers N (2 ≤ N ≤ 50) and M (0 ≤ M ≤ 500), which indicates the number of base stations and lines respectively. The following M lines describe the network structure. The i-th of them corresponds to the i-th network line and contains two integers ui and vi and a polynomial pi. ui and vi indicate the indices of base stations (1 ≤ ui, vi ≤ N); pi indicates the network bandwidth.

Each polynomial has the form of:

aLxL + aL-1xL-1 + ... + a2x2 + a1x + a0

where L (0 ≤ L ≤ 50) is the degree and ai's (0 ≤ i ≤ L, 0 ≤ ai ≤ 100) are the coefficients. In the input,

* each term aixi (for i ≥ 2) is represented as <ai>x^<i>
* the linear term (a1x) is represented as <a1>x;
* the constant (a0) is represented just by digits;
* these terms are given in the strictly decreasing order of the degrees and connected by a plus sign ("+");
* just like the standard notations, the <ai> is omitted if ai = 1 for non-constant terms;
* similarly, the entire term is omitted if ai = 0 for any terms; and
* the polynomial representations contain no space or characters other than digits, "x", "^", and "+".



For example, 2x2 + 3x + 5 is represented as 2x^2+3x+5; 2x3 + x is represented as 2x^3+x, not 2x^3+0x^2+1x+0 or the like. No polynomial is a constant zero, i.e. the one with all the coefficients being zero.

The end of input is indicated by a line with two zeros. This line is not part of any dataset.

Output

For each dataset, print the maximal bandwidth as a polynomial of x. The polynomial should be represented in the same way as the input format except that a constant zero is possible and should be represented by "0" (without quotes).

Example

Input

3 3
1 2 x+2
2 3 2x+1
3 1 x+1
2 0
3 2
1 2 x
2 3 2
4 3
1 2 x^3+2x^2+3x+4
2 3 x^2+2x+3
3 4 x+2
0 0


Output

2x+3
0
2
x+2
#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;
}

