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*.

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

*N M*

*u*_{1} *v*_{1} *p*_{1}

...

*u*_{M} *v*_{M} *p*_{M}

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 *u _{i}* and

Each polynomial has the form of:

*a _{L}x^{L}* +

where *L* (0 ≤ *L* ≤ 50) is the degree and *a _{i}*'s (0 ≤

- each term
*a*(for_{i}x^{i}*i*≥ 2) is represented as <*a*>_{i}*x*^<*i*> - the linear term (
*a*_{1}*x*) is represented as <*a*_{1}>*x*; - the constant (
*a*_{0}) 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 <
*a*> is omitted if_{i}*a*= 1 for non-constant terms;_{i} - similarly, the entire term is omitted if
*a*= 0 for any terms; and_{i} - the polynomial representations contain no space or characters other than digits, "x", "^", and "+".

For example, 2*x*^{2} + 3*x* + 5 is represented as 2x^2+3x+5; 2*x*^{3} + *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.

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).

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

2x+3 0 2 x+2

Source: ACM International Collegiate Programming Contest
, ACM-ICPC Japan Alumni Group Practice Contest 2011, Tokyo, 2011-11-06

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/