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:
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 ≤ 104) 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 ≤ 104). The following m lines contains the numbers _a_, _b_ (1 ≤ a < b ≤ n) and integers _d_, _nr_ (0 < d ≤ 105, 0 < nr ≤ 106) 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).
## Input
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 ≤ 104) 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 ≤ 104). The following m lines contains the numbers _a_, _b_ (1 ≤ a < b ≤ n) and integers _d_, _nr_ (0 < d ≤ 105, 0 < nr ≤ 106) 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.
## Output
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).
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the number of objects, $ k \in \mathbb{Z} $ the number of targets ($1 \leq k < n$).
- Targets are objects $ \{1, 2, \dots, k\} $; source is object $ n $.
- Let $ G = (V, E) $ be an undirected graph with $ V = \{1, 2, \dots, n\} $.
- Each edge $ e \in E $ is a triple $ (a, b, d, \text{nr}) $, where $ 1 \leq a < b \leq n $, $ d > 0 $ is distance, $ \text{nr} > 0 $ is non-resistance.
- Multiple edges between same pair allowed.
**Constraints**
1. $ 0 \leq T \leq 20 $
2. For each test case:
- $ 2 \leq n \leq 10^4 $, $ 1 \leq k < n $
- $ 1 \leq m \leq 10^4 $
- $ 0 < d \leq 10^5 $, $ 0 < \text{nr} \leq 10^6 $
**Objective**
For each target $ t \in \{1, 2, \dots, k\} $, determine if there exists a path from $ t $ to $ n $.
For any path $ P $ from $ t $ to $ n $, define its **power** as $ \min_{e \in P} \text{nr}(e) $.
A target $ t $ is **in danger** if the **maximum power** over all paths from $ t $ to $ n $ is **positive** (i.e., at least one path exists).
**Output**
For each test case, output all targets $ t \in \{1, \dots, k\} $ that are in danger, in ascending order.