이동통신망의 최대 대역폭

스마트폰 때문에 인터넷 트래픽이 계속 늘고 있다. 이동통신 사업자는 통신망을 증설해야 한다.

한 사업자의 통신망은 기지국 여러 개와 회선 여러 개로 이루어진다. 회선 하나는 기지국 두 개를 양방향으로 잇는다. 회선의 대역폭은 해마다 늘어나고, 연도 $x$의 다항식 $f(x)$로 주어진다.

통신망 구조가 주어질 때 1번 기지국과 $N$번 기지국 사이의 최대 대역폭을 $x$의 다항식으로 구하는 프로그램을 작성하라.

두 기지국 사이의 트래픽은 여러 경로로 나누어 보낼 수 있다. 한 회선을 지나는 트래픽의 합은 그 회선의 대역폭을 넘지 못하므로, 최대 대역폭은 1번 기지국에서 $N$번 기지국으로 흘릴 수 있는 최대 유량과 같다.

어느 회선이 병목인지는 $x$ 값에 따라 달라진다. 충분히 큰 모든 $x$에서 최대 대역폭과 값이 같은 다항식은 하나뿐이고, 그 다항식을 출력한다.

입력은 데이터 세트 여러 개로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

N M
u1 v1 p1
...
uM vM pM

첫 줄에는 기지국 수 $N$ ($2 \le N \le 50$)과 회선 수 $M$ ($0 \le M \le 500$)이 주어진다. 이어지는 $M$개의 줄은 통신망 구조를 나타낸다. $i$번째 줄에는 기지국 번호 $u_i$와 $v_i$ ($1 \le u_i, v_i \le N$), 그리고 대역폭을 나타내는 다항식 $p_i$가 주어진다. 같은 기지국 쌍을 잇는 회선이 여러 개일 수 있고, 두 끝이 같은 기지국인 회선도 있을 수 있다.

다항식의 형태는 다음과 같다.

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

$L$ ($0 \le L \le 50$)은 차수이고, $a_i$ ($0 \le i \le L$, $0 \le a_i \le 100$)는 계수이다. 입력에서 다항식은 다음 규칙으로 적는다.

• 차수가 $2$ 이상인 항 $a_i x^i$는 <a_i>x^<i>로 적는다.
• 일차항 $a_1 x$는 <a_1>x로 적는다.
• 상수항 $a_0$은 숫자만 적는다.
• 항은 차수가 큰 것부터 작은 것 순서로 적고 +로 잇는다.
• 상수항이 아닌 항은 계수가 $1$이면 계수를 적지 않는다.
• 계수가 $0$인 항은 통째로 적지 않는다.
• 다항식에는 공백이 없고, 숫자와 x, ^, + 외의 문자도 없다.

$2x^2 + 3x + 5$는 2x^2+3x+5로 적고, $2x^3 + x$는 2x^3+x로 적는다. 2x^3+0x^2+1x+0처럼 적지 않는다. 계수가 모두 $0$인 다항식은 입력에 주어지지 않는다.

입력의 끝은 $0$ 두 개가 적힌 줄로 나타낸다. 이 줄은 데이터 세트가 아니다.

각 데이터 세트마다 최대 대역폭을 $x$의 다항식으로 한 줄에 출력한다. 표기 규칙은 입력과 같다. 다만 결과는 상수 $0$일 수 있고, 이때는 0을 출력한다.