도로 계획

비순환(사이클이 없는) 도로망은 방향이 있는 도로 구간(간선)들로 이루어지며, 각 구간은 전체 $N$개의 교차로(정점) 중 두 교차로를 잇는다. 한 도로 구간을 지나는 데 걸리는 시간은 항상 양수이고, 그 구간을 이용하는 자동차의 수 $C$에 선형으로 의존한다.

$T(s) = a_s \cdot C + b_s$

$a_s$와 $b_s$는 도로 구간 $s$의 성질을 나타내는 두 상수이며, 단정밀도 부동소수점 수로 표현된다. 교차로를 지나는 데 걸리는 시간은 $0$이다.

여러 대의 자동차가 이 도로망에서 정점 $0$에서 정점 $N-1$로 이동해야 한다. 각 자동차는 자신의 이동 시간을 줄이기 위해 이기적으로 경로를 고르며, 다른 모든 자동차 역시 이기적으로 경로를 고른다는 사실을 알고 있다. 가능한 각 경로마다 몇 대의 자동차가 지나가는지, 그리고 그 경로들을 이동하는 데 걸리는 시간이 얼마인지를 계산하는 프로그램을 작성하시오.

입력에는 여러 개의 테스트가 들어 있으며, 다음과 같이 구성된다. 첫 줄에는 테스트의 개수가 주어진다. 이어지는 줄들에는 각 테스트의 명세가 주어진다. 각 테스트의 첫 줄에는 정점의 수, 간선의 수, 자동차의 수가 공백으로 구분되어 주어진다. 그다음 각 간선이 한 줄에 하나씩 주어지며, 다음 값들이 공백으로 구분되어 있다: 출발 정점, 도착 정점, $a_s$, $b_s$.

각 테스트 입력마다 한 줄씩 출력하며, 그 도로망에서 어떤 자동차가 이동하는 데 걸리는 최소 시간을 소수점 이하를 버려(내림하여) 정수로 출력한다.

첫 번째 입력은 정점 $4$개와 간선 $4$개로 이루어지며, $4000$대의 자동차가 정점 $0$에서 정점 $3$으로 이동해야 한다. 이동 시간을 가장 작게 만들기 위해, 자동차들은 가능한 두 경로 $(0 \to 1 \to 3)$과 $(0 \to 2 \to 3)$ 중 하나를 골라 두 경로에 같은 수의 자동차가 지나가도록 나뉜다. 따라서 최소 이동 시간은 $\lfloor 0.01 \times 2000 + 45.1 \rfloor = 65$이다.

두 번째 입력은 첫 번째와 비슷하지만, 정점 $1$과 정점 $2$ 사이에 비용이 $0$인 간선이 하나 추가되어 있다. 이 경우 모든 자동차가 이기적으로 경로 $(0 \to 1 \to 2 \to 3)$을 선택하며, 최소 이동 시간은 $80$이 된다.