입력 조건이 아래와 같이 a<b라고 설명이 되어있는데, a==b 인 테스트 케이스가 존재하는 것 같습니다.

"다음 이어 나오는 M개의 각 줄에는 도로(a, b)와 그 통과시간 t가 a b t 로 표시된다. 단 이 경우 a < b 이고 1 ≤ t ≤ 10000이다."

문제 조건을 수정하거나 테스트 케이스를 조정해야하지 않을까 싶습니다