Problem Description

Some people say, “Any two people in the world can be connected through at most $6$ people.” Little B is very interested in this, so he started some research on relationship mining in social networks.

Now Little B has obtained social network testdata containing $N$ people, with $M$ pieces of relationship information. A relationship can be represented as $(a_i, b_i, w_i)$, meaning that there is a relationship between people $a_i$ and $b_i$, and the closeness is $w_i$ ($w_i>0$). Little B now wants to choose $K$ people ($K\leq N$) as research targets. To make the research more reliable, he hopes that the total closeness of relationships among these $K$ people is 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 \wedge a_i\in S \wedge b_i \in S} w_i$$

Input Format

This is an output-only problem. There are $10$ input files relation*.in in your directory.

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

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

Output Format

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

The output file should contain $K$ lines, each with one integer, indicating the index of one of the selected $K$ people.

3 2 2
1 2 3
1 3 5 

1
3 

Hint

Scoring.

For each test point, if you do not output anything or your output is invalid, you get $0$ points.

For each test point, there are four scoring parameters $m_1$, $m_2$, $m_3$, and $m_4$. Suppose the sum of closeness values among 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\geq m_2$, you get $8$ points.
• If $m_2>c\geq m_3$, you get $5$ points.
• If $m_3>c\geq m_4$, you get $3$ points.
• If $c>0$, you get $1$ point.
• Otherwise, you get $0$ points.

Translated by ChatGPT 5