텔레포트
시간 제한1초메모리 제한128 MB
순간이동 통로가 없을 때의 최단 경로 정보와, 그 통로를 포함해 측정된 이동 시간들을 이용해 순간이동 통로가 연결하는 두 방을 찾는 문제입니다.
문제
우주선은 방과 그 방들을 잇는 복도로 이루어져 있다. 각 복도에는 지나가는 데 걸리는 시간이 정해져 있고, 방 안을 지나가는 시간은 걸리지 않는다.
서로 다른 두 방 사이에는 순간 이동 장치가 하나 설치되어 있다. 이 장치를 이용하면 두 방 사이를 시간 없이 이동할 수 있다. 루시는 서로 다른 방 쌍 사이를 K번 이동했고, 매번 복도와 순간 이동 장치를 함께 고려했을 때 가능한 최단 시간으로 이동했다. 각 이동에 대해 출발 방, 도착 방, 실제로 걸린 시간이 주어진다.
순간 이동 장치가 설치된 두 방의 번호를 찾아라.
입력
첫째 줄에 방의 수 N과 복도의 수 M이 주어진다. 1 <= N <= 200, 1 <= M <= 20000이다.
다음 M개의 줄에는 정수 A, B, T가 공백으로 구분되어 주어진다. 이는 방 A와 방 B가 복도로 연결되어 있고, 그 복도를 지나가는 데 T초가 걸린다는 뜻이다.
다음 줄에는 루시가 기록한 이동 횟수 K가 주어진다. 1 <= K <= 5000이다.
다음 K개의 줄에는 정수 A, B, T가 공백으로 구분되어 주어진다. 이는 루시가 방 A에서 방 B까지 이동하는 데 T초가 걸렸다는 뜻이다.
정답은 항상 존재하며 하나로 정해진다.
출력
순간 이동 장치가 설치된 두 방의 번호를 한 줄에 출력한다. 더 작은 번호를 먼저 출력하고, 두 번호는 공백 하나로 구분한다.