Задачі
Mobile Network
Mobile Network
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).
Вхідні дані #1
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
Вихідні дані #1
2x+3 0 2 x+2