시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 36 17 15 71.429%

문제

대구과학고에서는 dgeu-learning이라는 Wi-Fi망을 이용할 수 있다. 하지만 이를 대가로 대구광역시교육청은 컴퓨터에 내PC보안점검 프로그램을 강제로 깔아버린다. 게다가 속도도 느려터졌다! 결국은 dgeu-learning으로 학습 프로그램 league of legends를 이용하다 속이 터진 다운이가 자체적인 인터넷 시스템을 만들기로 결심하게 된다.

다운이는 먼저 대곽인 N명의 컴퓨터(1번부터 N번까지로 번호붙여져 있다)를 총 M개의 LAN선으로 연결하였다. LAN선은 연결된 두 컴퓨터 사이에 자유롭게 데이터를 전송하게 해 준다. LAN선들의 데이터 전송 속도는 다양하며, 모든 컴퓨터들은 LAN선을 통해 직‧간접적으로 연결되어 있다. 다운이는 먼저 P2P 통신(컴퓨터 간 통신)을 실험해보기로 한다.

어떤 두 컴퓨터 A, B(A≠B)가 서로 데이터를 주고받는다고 생각해보자. A, B를 연결하는 LAN선으로 이루어진 경로는 항상 존재한다. 어떤 경로를 통한 데이터 전송 속도는 이 경로를 이루는 LAN선들의 전송 속도의 최솟값이 될 것이다. 만약 A와 B를 연결하는 경로가 여러 개 있다면, 다운이가 만든 인터넷 시스템은 가장 높은 전송 속도를 얻을 수 있는 경로를 자동으로 고를 것이다.

다운이는 자신의 시스템이 잘 동작하는지 테스트하기 위해, 두 컴퓨터를 고르고 데이터 전송 속도를 측정하는 작업을 반복할 것이다. 다운이의 시스템이 잘 작동한다면 얼마만큼의 통신 속도가 나와야 할지 계산하자.

입력

첫 줄에는 다운이가 만든 시스템의 컴퓨터의 수 N과 LAN선의 수 M, 그리고 다운이가 테스트할 횟수 Q가 주어진다. (2≤N≤200,000, N-1≤M≤500,000, 1≤Q≤200,000)

둘째 줄부터 M개의 줄에는 다운이의 LAN선들이 연결하는 두 컴퓨터의 번호 A, B와 통신 속도 V를 나타내는 세 정수가 공백을 사이에 두고 주어진다. (1≤A,B≤N, A≠B, 1≤V≤109) 서로 같은 A, B의 쌍이 여러 번 주어질 수 있음에 유의하라. 이는 A와 B를 연결하는 LAN선이 여럿 있음을 뜻한다.

이어지는 Q개의 줄에, 다운이가 데이터 전송 속도를 테스트할 두 컴퓨터의 번호 A, B가 주어진다. (1≤A,B≤N, A≠B)

출력

Q개의 줄에, 두 컴퓨터 A, B 사이의 데이터 전송 속도로 계산되는 값을 순서대로 출력한다.

서브태스크 1 (22점)

Q=1를 만족한다.

서브태스크 2 (23점)

N≤400을 만족한다.

서브태스크 3 (24점)

M=N-1를 만족한다. 이 때의 인터넷망은 트리 그래프가 가지는 특별한 성질들을 가지게 된다.

서브태스크 4 (11점)

문제에 제시된 조건 이외의 다른 제약은 없다.

예제 입력 1

6 8 6
1 2 7
1 3 3
1 5 1
1 6 4
2 3 5
3 4 2
3 5 2
4 5 6
1 2
3 1
6 5
3 6
4 5
1 4

예제 출력 1

7
5
2
4
6
2

채점

  • 예제는 채점하지 않는다.