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\textbf{ f(x)} of the year \textbf{x}. Your task is, given the network structure, to write a program to calculate the maximal bandwidth between the \textbf{1}-st and \textbf{N}-th base stations as a polynomial of \textbf{x}. \InputFile The input consists of multiple datasets. Each dataset has the following format: \textbf{N Mu_1 v_1 p_1...u_M v_M p_M} The fi rst line of each dataset contains two integers \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{50}) and \textbf{M} (\textbf{0} ≤ \textbf{M} ≤ \textbf{500}), which indicates the number of base stations and lines respectively. The following \textbf{M} lines describe the network structure. The \textbf{i}-th of them corresponds to the \textbf{i}-th network line and contains two integers \textbf{u_i} and \textbf{v_i} and a polynomial \textbf{p_i}. \textbf{u_i} and \textbf{v_i} indicate the indices of base stations (\textbf{1} ≤ \textbf{u_i}, \textbf{v_i} ≤ \textbf{N}); \textbf{p_i} indicates the network bandwidth. Each polynomial has the form of: \textbf{a_Lx^L + a_\{L-1\}x^\{L-1\} + ... + a_2x^2 + a_1x + a_0} where \textbf{L} (\textbf{0} ≤ \textbf{L} ≤ \textbf{50}) is the degree and ai's (\textbf{0} ≤ \textbf{i} ≤ \textbf{L}, \textbf{0} ≤ \textbf{a_i} ≤ \textbf{100}) are the coecients. In the input, \begin{itemize} \item each term \textbf{a_ix^i} (for \textbf{i} ≥ \textbf{2}) is represented as \textbf{< a_i >x} \textbf{^} \includegraphics{https://static.e-olymp.com/content/c0/c0dcc1b123a5503fd700b0ed8b5f1f3426f72184.jpg} ; \item the linear term \textbf{(a_1x)} is represented as \textbf{< a_1 >x }; \item the constant \textbf{(a_0)} is represented just by digits; \item these terms are given in the strictly decreasing order of the degrees and connected by a plus sign ("\textbf{+}"); \item just like the standard notations, the \textbf{< a_i >} is omitted if \textbf{a_i = 1} for non-constant terms; \item similarly, the entire term is omitted if \textbf{a_i = 0} for any terms; and \item the polynomial representations contain no space or characters other than digits, "\textbf{x}", "\textbf{^}",and "\textbf{+}". \end{itemize} For example, \textbf{2x^2 + 3x + 5} is represented as \textbf{2x^2+3x+5}; \textbf{2x^3 + x} is represented as \textbf{2x^3+x}, not \textbf{2x^3+0x^2+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. \OutputFile For each dataset, print the maximal bandwidth as a polynomial of \textbf{x}. The polynomial should be represented in the same way as the input format except that a constant zero is possible andshould be represented by "\textbf{0}" (without quotes).