학교 탐방하기

국희는 여름방학 동안 고등학생에게 학교 건물을 소개하는 일을 맡았다. 학교가 산비탈에 있어서 건물을 잇는 길은 오르막길이거나 내리막길이다. 국희는 입구를 기준으로 각 길이 오르막인지 내리막인지 미리 조사해 두었다.

건물에는 $1$번부터 $N$번까지 번호를 붙였고, 입구에는 $0$번을 붙였다. 입구에서 뻗어 나온 길은 하나뿐이며 그 길은 $1$번 건물로 이어진다.

모든 건물을 소개하려면 입구와 $N$개의 건물을 전부 잇는 길을 골라야 한다. 국희는 이 조건을 지키면서 고르는 길의 수를 최소로 한다. 장소가 모두 $N+1$개이므로 고르는 길은 정확히 $N$개이고, 고른 $N$개의 길만으로 입구에서 모든 건물에 갈 수 있어야 한다.

피로도는 고른 길에 포함된 오르막길의 개수 $k$로 정해지며 $k^2$이다. 오르막인지 내리막인지는 처음 조사한 결과로만 판단한다. 즉 내리막길을 내려갔다가 되돌아 올라오는 경우는 세지 않는다. 입구와 $1$번 건물을 잇는 길도 항상 고른 길에 들어가므로 피로도 계산에 포함된다.

고를 수 있는 조합 가운데 피로도가 가장 큰 조합과 가장 작은 조합이 있다. 두 피로도의 차이를 구하라.

첫 줄에 건물의 개수 $N$($1 \le N \le 1000$)과 건물 사이 길의 개수 $M$($1 \le M \le N(N-1)/2$)이 주어진다.

둘째 줄에는 입구와 $1$번 건물을 잇는 길이 $A$ $B$ $C$ 형식으로 주어진다. $A$는 항상 $0$, $B$는 항상 $1$이다.

이어지는 $M$개의 줄에는 $A$ $B$ $C$가 주어진다. $A$번 건물과 $B$번 건물을 잇는 길이 있다는 뜻이며($1 \le A, B \le N$, $A \ne B$), $C$는 오르막길이면 $0$, 내리막길이면 $1$이다.

같은 두 건물을 잇는 길이 두 번 이상 주어지는 경우는 없다. 입구에서 모든 건물로 갈 수 있음이 보장된다.

피로도가 가장 큰 조합과 가장 작은 조합의 피로도 차이를 한 줄에 출력한다.