Mobile Network Bandwidth

Internet traffic keeps growing because of smartphones, so wireless carriers have to expand their networks.

The network of a carrier consists of base stations and lines. Each line connects two base stations in both directions. The bandwidth of a line grows every year and is given as a polynomial $f(x)$ of the year $x$.

Given the structure of the network, compute the maximum bandwidth between base station 1 and base station $N$ as a polynomial of $x$.

The traffic between the two stations can be split over several routes. The traffic on a line cannot exceed the bandwidth of that line, so the maximum bandwidth equals the maximum flow from station 1 to station $N$.

Which line is the bottleneck depends on $x$. Exactly one polynomial equals the maximum bandwidth for every sufficiently large $x$. Print that polynomial.

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

N M
u1 v1 p1
...
uM vM pM

The first line contains the number of base stations $N$ ($2 \le N \le 50$) and the number of lines $M$ ($0 \le M \le 500$). The next $M$ lines describe the network. The $i$-th of them contains the station indices $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$) and the polynomial $p_i$ that gives the bandwidth of the line. Several lines may connect the same pair of stations, and a line may have both of its ends at the same station.

A polynomial has the form

$a_L x^L + a_{L-1} x^{L-1} + \cdots + a_1 x + a_0$

where $L$ ($0 \le L \le 50$) is the degree and $a_i$ ($0 \le i \le L$, $0 \le a_i \le 100$) are the coefficients. The input writes a polynomial by these rules.

• A term $a_i x^i$ with $i \ge 2$ is written as <a_i>x^<i>.
• The linear term $a_1 x$ is written as <a_1>x.
• The constant term $a_0$ is written as digits only.
• The terms are written in strictly decreasing order of degree and joined by +.
• For a term other than the constant one, the coefficient is omitted when $a_i = 1$.
• A term with $a_i = 0$ is omitted entirely.
• A polynomial contains no space and no character other than digits, x, ^, and +.

So $2x^2 + 3x + 5$ is written as 2x^2+3x+5, and $2x^3 + x$ is written as 2x^3+x, never as 2x^3+0x^2+1x+0. No polynomial in the input has all coefficients equal to $0$.

The end of the input is a line with two zeros. That line is not a dataset.

For each dataset, print the maximum bandwidth as a polynomial of $x$ on one line. Use the same notation as the input, except that the answer may be the constant $0$, which is printed as 0.