It is said that "any two people in the world can be connected through at most 6 people." Little B is very interested in this and has started research on relationship mining in social networks.

Little B has obtained social network data containing $N$ people, with $M$ pieces of relationship information in the network. A piece of relationship information can be represented as $(a_i, b_i, w_i)$, indicating that there is a relationship between $a_i$ and $b_i$ with a closeness of $w_i$ ($w_i > 0$). Little B wants to select $K$ ($K \le N$) people as research subjects. To ensure the research has high credibility, Little B wants the sum of the closeness of the relationships between these $K$ people to be as large as possible.

This problem can be abstracted as: given a weighted undirected graph $G=(V, E)$ and an integer $K$, the goal is to find a subset $S$ of the vertex set $V$ such that $|S| = K$, and the following expression is maximized:

$$\sum_{(a_i, b_i, w_i) \in E, a_i \in S, b_i \in S} w_i$$

Input

This is an answer-submission problem. There are 10 input files named relation*.in in your directory.

The first line of the input file contains three integers $N$, $M$, and $K$, representing the number of points (people) in the given social network, the number of edges (relationships), and the number of people $K$ to be selected, respectively.

The next $M$ lines each contain three positive integers $a_i$, $b_i$, and $w_i$, representing an edge (relationship). All points (people) are numbered from 1 to $N$.

Output

For each input file, provide the corresponding output file relation*.out in the directory.

The output file should contain $K$ lines, each containing an integer representing the ID of one of the $K$ selected people.

Examples

Input 1

3 2 2 
1 2 3 
1 3 5

Output 1

1 
3

Subtasks

For each test case, we have four scoring parameters $m_1, m_2, m_3,$ and $m_4$. Assuming the sum of the closeness of the relationships between the $K$ people selected by the contestant is $c$:

• If $c > m_1$, you get 12 points;
• If $c = m_1$, you get 10 points;
• If $m_1 > c \ge m_2$, you get 8 points;
• If $m_2 > c \ge m_3$, you get 5 points;
• If $m_3 > c \ge m_4$, you get 3 points;
• If $c > 0$, you get 1 point;
• Otherwise, you get 0 points.

Note

For each test case, if you do not provide an output or the output is invalid, you will receive 0 points.

There is a program named checker in your directory that can be used to check your output. You can use the following command in the terminal to check your output:

./checker N

where $N$ is the test case number. For example, to test the 3rd test case, you can use:

./checker 3

This program will check if your output is valid. If the solution is valid, the program will also output the sum of the closeness for that solution.