Fare and Balanced

교통 혼잡을 해결하는 일은 젊은 도시 계획가에게 쉽지 않은 과제다. 수많은 운전자가 저마다 다른 목적을 가지고 각자 선택해서 움직이면, 그 결과는 때로 예측 가능하고 때로는 무질서한 복잡한 시스템이 된다. 당신은 헌신적인 공무원으로서 여러 도로에 걸친 출근 시간대 교통을 최적화하는 임무를 맡았다.

모든 도로는 주거 지역과 도심 상업 지구 사이에 놓여 있다. 아침에 주거 지역에 사는 사람은 각자 상업 지구까지 가는 경로를 운전한다. 특정 도로의 아침 통근 교통은 한 방향으로만 흐르며, 어떤 경로에도 순환은 없다(아침 운전자는 되돌아가지 않는다).

도로마다 주행에 걸리는 시간이 다르므로 경로마다 빠르고 느린 차이가 생긴다. 운전자는 빠른 경로를 훨씬 더 선호하고, 그 결과 해당 도로에 혼잡이 생긴다. 교통량을 최대한 고르게 나누기 위해 일부 도로에 통행료를 부과하여, 모든 경로가 운전자가 체감하는 "비용"이 같아지도록 한다. 다만 운전자에게 지나친 불편을 주지 않도록, 어떤 경로를 택하더라도 같은 운전자가 통행료를 두 번 내서는 안 된다.

그림 5는 주거 지역(교차로 1)에서 도심 상업 지구(교차로 4)까지 경로를 이루는 도로 다섯 개를 보여 준다. 각 도로의 주행 비용은 굵은 파란색 글씨로 적혀 있다. 점선 화살표는 1에서 4까지 가능한 세 경로를 나타낸다. 처음에 경로의 비용은 10, 8, 12이다. 1과 4를 잇는 도로에 비용 2의 통행료를, 3과 4를 잇는 도로에 비용 4의 통행료를 더하면 각 경로의 비용이 모두 12가 된다.

그림 5: 교차로 1의 주거 지역과 교차로 4의 도심 상업 지구를 잇는 도로

시작점에서 도착점까지 모든 경로의 비용(주행 시간 비용 + 통행료)이 같고, 어떤 경로에도 통행료 도로가 둘 이상 포함되지 않도록 어느 도로에 통행료를 매길지, 각 통행료를 얼마로 할지 정해야 한다. 통행료는 최종 비용이 최소가 되도록 골라야 한다. 상황에 따라서는 위 조건을 만족하는 통행료를 매기는 것이 불가능할 수도 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 교차로의 수 $N$ (2 ≤ $N$ ≤ 50000)과 도로의 수 $R$ (1 ≤ $R$ ≤ 50000)이 적힌 줄로 시작한다. 이어지는 $R$개의 줄에는 정수 $x_i$, $y_i$, $c_i$ (1 ≤ $x_i$, $y_i$ ≤ $N$, 1 ≤ $c_i$ ≤ 1000)가 주어진다. 이는 $i$번 도로로 아침 교통이 교차로 $x_i$에서 교차로 $y_i$로 가며, 기본 주행 시간 비용이 $c_i$임을 뜻한다. 교차로 1은 출발지인 주거 지역이고, 교차로 $N$은 목적지인 상업 지구다. 도로는 입력 순서대로 1부터 $R$까지 번호가 붙는다. 모든 교차로는 1에서 $N$까지 가는 경로에 속하며, 순환은 없다.

마지막 테스트 케이스 다음 줄에는 0 두 개가 적혀 있다.

각 테스트 케이스마다 케이스 번호(1부터 시작), 통행료를 부과할 도로의 수 $T$, 모든 경로의 최종 비용을 한 줄에 출력한다. 이어지는 $T$개의 줄에는 도로 번호 $i$와 그 도로에 부과할 양의 통행료를 출력한다. 최소 비용 해가 여러 개라면 어느 것을 출력해도 된다. 해가 없으면 No solution을 출력한다. 출력 형식은 예제 출력을 따른다.