자매 도시

인도네시아에는 N 개의 도시가 있고, 0부터 N - 1까지 번호가 매겨져 있다. 또 M 개의 양방향 도로가 있는데, 0 부터 M - 1까지 번호가 매겨져 있다. 각 도로는 두 개의 서로 다른 도시를 연결한다. i 번 도로는 U[i] 번 도시와 V[i] 번 도시를 연결하고, 자동차로 여행하려면 휘발유 W[i] 만큼이 필요하다. 어떤 두 도시도 서로 오갈 수 있도록 도로망이 구축되어 있다.

앞으로 Q 일 동안, 매일매일 한 쌍의 도시가 자매 도시 관계를 맺으려고 한다. 구체적으로는, j번째 날, X[j] 번 도시는 Y[j] 번 도시와 자매 도시 관계를 맺으려고 한다. 이러려면, X[j] 번 도시는 대표단을 자동차를 이용해서 Y[j] 번 도시로 보낸다. 비슷하게, Y[j] 번 도시도 대표단을 자동차를 이용해서 X[j] 번 도시로 보낸다.

혼잡을 막기 위해서, 두 자동차는 어느 순간에도 만나면 안된다. 보다 구체적으로는, 두 자동차가 동시에 같은 도시에 있으면 안된다. 또, 같은 도로를 동시에 서로 반대 방향으로 여행해도 안된다. 추가로, 어떤 도로를 여행하는 자동차는 이 도로를 끝까지 가서 목적지에 도착해야 한다. (다른 말로 하면, 도로 중간에서 유턴할 수 없다.) 그렇지만, 자동차는 같은 도시 또는 같은 도로를 한 번 이상 방문할 수 있다. 또, 자동차는 언제든지 어떤 도시에서든지 대기할 수 있다.

연료 탱크가 큰 자동차는 비싸기 때문에, 두 도시는 사용할 두 자동차의 연료 탱크의 최대 용량을 최소화하는 경로를 택하고 싶다. 각각의 도시에는 무한히 많은 휘발유가 있는 주유소가 있기 때문에, 자동차가 필요한 연료 탱크의 최대 용량은 자동차가 이용할 모든 도로에서 최대로 필요한 휘발유의 양이다.

문제

제한