두 가지 교통수단

JOI 나라에는 0번부터 N − 1번까지 번호가 붙은 N개의 도시가 있다. 0번부터 A − 1번까지 번호가 붙은 A개의 철도 노선이 있다. 철도 노선 i (0 ≤ i ≤ A − 1)는 도시 Ui와 도시 Vi를 양방향으로 연결하며 요금은 Ci이다. 서로 다른 철도 노선은 서로 다른 두 도시를 연결한다. 0번부터 B − 1번까지 번호가 붙은 B개의 버스 노선이 있다. 버스 노선 j (0 ≤ j ≤ B − 1)는 도시 Sj와 도시 Tj를 양방향으로 연결하며 요금은 Dj이다. 서로 다른 버스 노선은 서로 다른 두 도시를 연결하지만, 철도 노선과 버스 노선이 같은 두 도시를 연결할 수도 있다. 철도와 버스를 적절히 이용하면 임의의 두 도시 사이를 이동할 수 있다.

Azer는 도시 0에서 각 도시로 이동하는 데 필요한 최소 총 요금을 알고 싶어 한다. Azer는 철도 노선에 대한 정보만 알고 있고, 버스 노선에 대한 정보만 알고 있는 Baijan과 협력한다.

두 사람은 문자 0 또는 1을 주고받아 의사소통한다. 주고받는 문자의 총 개수는 58 000개 이하여야 한다.

철도 노선 정보를 받은 Azer의 프로그램과 버스 노선 정보를 받은 Baijan의 프로그램이 서로 의사소통하여, Azer가 도시 0에서 각 도시로 이동하는 데 필요한 최소 총 요금을 구하도록 하는 프로그램을 작성하라.

샘플 그레이더는 다음 형식으로 표준 입력에서 입력 데이터를 읽는다.

N A B
U0 V0 C0
.
.
.
UA−1 VA−1 CA−1
S0 T0 D0
.
.
.
SB−1 TB−1 DB−1

샘플 그레이더는 다음 정보를 표준 출력과 표준 오류에 출력한다(따옴표는 명확성을 위해 표기한 것이다).

• 프로그램이 Wrong Answer [1] 또는 Wrong Answer [2]로 판정되면 그 종류를 표준 오류에 “Wrong Answer [1]”과 같이 출력한다. 표준 출력에는 아무것도 출력하지 않는다.

• 그렇지 않으면 주고받은 문자의 총 개수 L을 표준 오류에 “Accepted: L”과 같이 출력한다. 또한 다음과 같이 답 Z를 표준 출력에 출력한다.

  Z[0]
  .
  .
  .
  Z[N - 1]
  

  샘플 그레이더는 Z의 값이 올바른지 확인하지 않는다.

프로그램이 여러 종류의 Wrong Answer로 판정되면 샘플 그레이더는 그중 하나만 보고한다.

• 1 ≤ N ≤ 2 000.
• 0 ≤ A ≤ 500 000.
• 0 ≤ B ≤ 500 000.
• 0 ≤ Ui ≤ N − 1 (0 ≤ i ≤ A − 1).
• 0 ≤ Vi ≤ N − 1 (0 ≤ i ≤ A − 1).
• Ui ≠ Vi (0 ≤ i ≤ A − 1).
• (Ui1, Vi1) ≠ (Ui2, Vi2)이고 (Ui1, Vi1) ≠ (Vi2, Ui2) (0 ≤ i1 < i2 ≤ A − 1).
• 0 ≤ Sj ≤ N − 1 (0 ≤ j ≤ B − 1).
• 0 ≤ Tj ≤ N − 1 (0 ≤ j ≤ B − 1).
• Sj ≠ Tj (0 ≤ j ≤ B − 1).
• (Sj1, Tj1) ≠ (Sj2, Tj2)이고 (Sj1, Tj1) ≠ (Tj2, Sj2) (0 ≤ j1 < j2 ≤ B − 1).
• 철도와 버스를 적절히 이용하면 임의의 두 도시 사이를 이동할 수 있다.
• 1 ≤ Ci ≤ 500 (0 ≤ i ≤ A − 1).
• 1 ≤ Dj ≤ 500 (0 ≤ j ≤ B − 1).