눈덩이 싸움 1

$N$개의 노드로 이루어진 무방향 가중치 그래프가 있다. IOI 기간에 $L$개의 나라가 눈덩이 싸움을 벌인다. 처음에 각 나라는 어느 한 노드에 요새를 하나씩 가진다.

시각 $0$에 각 나라가 병사를 내보내기 시작한다. 싸움의 규칙은 다음과 같다.

• 나라가 요새를 가진 노드에서는 그 요새에 연결된 모든 간선을 따라 병사가 같은 속도로 출발한다.
• 두 나라가 간선 위에서 만나면 두 나라는 멈추고 영원히 싸운다.
• 두 나라가 노드에서 만나면 두 나라는 멈추고 영원히 싸운다.
• 나라가 이미 싸움이 벌어지고 있는 노드에 도착하면 그 싸움에 합류한다.
• 나라가 어떤 노드에 다른 나라보다 먼저 도착하면, 그 나라가 그 노드에 요새를 짓고 규칙 1에 따라 노드의 간선을 따라 병사를 내보낸다.

한 노드에는 요새가 최대 하나만 있다. 두 나라가 같은 시각에 한 노드에 도착하면, 그 노드에 도착한 병사들은 멈춰 그곳에서 영원히 싸우고 더 이상 이동하지 않는다.

싸우게 되는 나라 쌍을 모두 구하라.

첫 줄에 세 정수 $N, L, M$ ($2 \le N \le 100\,000$, $2 \le L \le 50$, $1 \le M \le 100\,000$)이 주어진다. 각각 노드의 수, 나라의 수, 간선의 수이다. 다음 $L$개의 줄에는 각 나라의 시작 노드 번호가 주어진다. 다음 $M$개의 줄에는 세 정수 $a, b, w$ ($0 \le a,b < N$, $a \neq b$, $1 \le w \le 2\,000$)가 주어진다. 이는 노드 $a$와 $b$ 사이에 길이가 $w$인 무방향 간선이 있다는 뜻이다. 노드 번호는 0부터 시작한다. 두 노드 사이에 간선은 최대 하나만 있으며, 서로 다른 두 나라가 같은 노드에서 시작하지 않는다.

싸우는 나라 쌍 $a, b$마다 한 줄에 a b를 출력한다. 여기서 $a < b$이며 나라 번호는 0부터 시작한다. 출력은 첫 번째 번호 기준으로 오름차순이어야 한다. 예를 들어 $L = 3$이고 세 나라가 모두 싸우면 다음과 같이 출력한다.

0 1
0 2
1 2