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

      N M

      u₁ v₁ p₁

      .

      .

      .

      u_M v_M p_M

The first 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 v_i and a polynomial p_i. u_i and v_i
indicate the indices of base
stations (1 <= u_i,v_i <= N); p_i indicates the network bandwidth.

Each polynomial has the form of:


a_Lx^L + a_L-1x^L-1 + ... + a₂x² + a₁x + a₀


where L (0 <= L <= 50) is the degree and a_i
's (0 <= i <= L, 0 <= a_i <= 100) are the coecients. In the input,


   • each term a_ixⁱ
(for i >= 2) is represented as h ﹤a_i﹥x^﹤i﹥;


   • the linear term (a_1x) is represented as ﹤a₁﹥;

   •  the constant (a₀) 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﹥ is omitted if a_i = 1 for non-constant terms;

   • similarly, the entire term is omitted if a_i = 0 for any terms; and

   • the polynomial representations contain no space or characters other than digits, "x", "^",
and "+".


For example, 2x² + 3x + 5 is represented as 2x^2+3x+5; 2x³ + x is represented as 2x^3+x,
not 2x^3+0x2+1x+0 or the like. No polynomial is a constant zero, i.e. the one with all the
coecients 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).

Migrated from old NTUJ.

JAG 模擬地区予選