Under construction

Still being built. Things may change

Snowball Fight 1

Time limit2sMemory limit1024 MB

Summary
Given a weighted graph with L countries starting at fixed nodes, find which pairs of countries end up fighting as their fighters spread.
Level

Medium7 of 10

Topics
Graph, Shortest path, Simulation
Solved
No attempts yet

Problem

An undirected, weighted graph with NN nodes is given. During IOI, LL countries have a snowball fight. At the start, each country has a fort at one node.

At time 00, every country starts sending out fighters. The fight follows these rules:

  • If a country owns a fort, its fighters leave the fort along every edge from it, all at the same speed.
  • If two countries meet along an edge, both stop and fight forever.
  • If two countries meet at a node, both stop and fight forever.
  • If a country reaches a node where countries are already fighting, it joins that fight.
  • If a country reaches a node before any other country, it builds a fort at that node and sends fighters out along the edges from the node by rule 1.

A node holds at most one fort. If two countries reach a node at the same time, the fighters who arrived there stop and fight there forever without moving on.

Determine which pairs of countries will fight each other.

Input

The first line contains three integers N,L,MN, L, M (2≤N≤100 0002 \le N \le 100\,000, 2≤L≤502 \le L \le 50, 1≤M≤100 0001 \le M \le 100\,000): the number of nodes, countries, and edges. The next LL lines each contain the node where a country starts. The next MM lines each contain three integers a,b,wa, b, w (0≤a,b<N0 \le a,b < N, a≠ba \neq b, 1≤w≤2 0001 \le w \le 2\,000), meaning there is an undirected edge of length ww between nodes aa and bb. Nodes are numbered from 0. There is at most one edge between any pair of nodes, and no two countries start on the same node.

Output

For each pair of countries a,ba, b that fight, print a line a b with a<ba < b. Countries are numbered from 0. Print the pairs sorted by the first index. For example, if L=3L = 3 and all three countries fight, the output is:

0 1
0 2
1 2

Examples5

  1. Example 1

    Input
    8 4 8
0
2
4
6
0 1 100
1 2 100
2 3 100
3 4 100
4 5 100
5 6 100
6 7 100
7 0 1000
    Expected output
    0 1
0 3
1 2
2 3

  2. Example 2

    Input
    4 3 3
0
1
2
0 3 100
1 3 100
2 3 100
    Expected output
    0 1
0 2
1 2

  3. Example 3

    Input
    4 3 3
0
1
2
0 3 100
1 3 100
2 3 1000
    Expected output
    0 1
0 2
1 2

  4. Example 4

    Input
    4 3 3
0
1
2
0 3 100
1 3 1000
2 3 1000
    Expected output
    0 1
0 2

  5. Example 5

    Input
    6 4 5
0
1
4
5
0 2 10
1 2 10
2 3 100
4 3 700
5 3 1000
    Expected output
    0 1
0 2
1 2
2 3