Mobile Network#3601

Mobile Network

30 sekunt

256 megabaýt

Örän kyn

The traffic 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$ .

Giriş

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

$N$ $M$ $u_{1}$ u_1 $v_{1}$ v_1 $p_{1}$ p_1 $\dots$ $u_{M}$ u_M $v_{M}$ v_M $p_{M}$ p_M

The first line of each dataset contains two integers $N$ ( $2 \leq N \leq 50$ 2 \le N \le 50) and $M$ ( $0 \leq M \leq 500$ 0 \le M \le 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}$ u_i and $v_{i}$ v_i and a polynomial $p_{i}$ p_i. $u_{i}$ u_i and $v_{i}$ v_i indicate the indices of base stations ( $1 \leq u_{i}, v_{i} \leq N$ 1 \le u_i, v_i \le N); $p_{i}$ p_i indicates the network bandwidth.

Each polynomial has the form of:

a_{L} x^{L} + a_{L - 1} x^{L - 1} + \dots + a_{2} x^{2} + a_{1} x + a_{0}

a_L x^L + a_{L-1} x^{L-1} + \ldots + a_2 x^2 + a_1 x + a_0

where $L$ ( $0 \leq L \leq 50$ 0 \le L \le 50) is the degree and $a_{i}$ a_i's ( $0 \leq i \leq L$ 0 \le i \le L, $0 \leq a_{i} \leq 100$ 0 \le a_i \le 100) are the coefficients. In the input,

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

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

Çykyş

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

Mysallar

1-nji mysal