dgeu-learning

대구과학고에서는 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 ≤ 10^9) 서로 같은 A, B의 쌍이 여러 번 주어질 수 있음에 유의하라. 이는 A와 B를 연결하는 LAN선이 여럿 있음을 뜻한다.

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

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