401484: GYM100482 D Lightning

The lightning usually hits towers, tall buildings. Have you noticed that? The thing is that they are near the“source of power”.

We will use this lightning model (which may be not true in real world). Every direct path in which the lightning can strike is characterized by its non-resistance (the bigger non-resistence, the bigger power of the lightning) and its length.

There are n objects (k of them are the targets at which the lightning can strike). We say the path has power x if the minimum non-resistence along the path is x.

The lightning could be modelled as follows:

1. The maximum power P the lightning can strike is calculated. It is the minimum non-resistence of a path with the biggest power from the source of power to the one of the k targets.
2. Then the minimum distance is calculated which has the path with power P from the source of power to the one of the k targets. It's guaranteed that it will be possible to find at least one such path.
3. All targets which have the path with minimum found distance with power P are called dangerous (because they are open for the strike).

The first line contains the number of test cases T (0 ≤ T ≤ 20). The first line of each test case contains the number of objects n (2 ≤ n ≤ 10⁴) and the number of targets k (1 ≤ k < n). Targets are objects numbered from 1 to k. The source of power is the object numbered n. The second line of each test case contains the number of direct paths m (1 ≤ m ≤ 10⁴). The following m lines contains the numbers a, b (1 ≤ a < b ≤ n) and integers d, nr (0 < d ≤ 10⁵, 0 < nr ≤ 10⁶) meaning that objects numbered a and b are connected by the direct path (with the distance d, non-resistence nr). Each direct path can be used by the lightning bidirectionally.

Note: the same pair of objects can be connected by more than one direct path.

For each test case output one line containing “Case #tc:”, where tc is the number of the test case (starting from 1). Then output all the targets which are in danger in the ascending order (separated by spaces).

1
3 2
2
3 1 2 3
2 3 1 2

Case #1: 1