Problem B
Communication Bases

Image by Pixabay from Pixabay

In a futuristic world, humans are at war with aliens. There are $N$ human bases numbered $1$ to $N$, and they are spread throughout the galaxy. Humans have set up $M$ bi-directional communication links between these bases, but some links have sustained damage from alien attacks. This has separated the human bases. You are given a list of communication links, and a score, $s$, for each of these links.

This score $s$ represents the amount of resources required to maintain the link. The higher the value of $s$, the more resources are needed to keep the link operational. While lower-resource links are cheaper to maintain, they tend to be less reliable under the current war conditions and are prone to breakdowns.

The human military has decided to prioritize reliable and resource efficient communication links. For this strategy to succeed, exactly $K$ connected components of bases are required. Therefore, any link with a resource score $s < T$ is considered too unreliable and must be deactivated, even if it is cheaper. Your task is to find the smallest threshold $T$ such that there are exactly $K$ connected components.

A connected component is a subset of bases such that for each pair of bases in the subset, there is a path involving one or more reliable links that leads from one base to the other. A single base that is not connected to any other base also forms a connected component.

Input

The input begins with a single line containing three space-separated integers: $N$, $M$, and $K$, where: $N$ represents the number of human bases ($1 \leq N \leq 10^5$), $M$ denotes the number of communication links ($1 \leq M \leq 10^6$), and $K$ is the number of components required ($1 \leq K \leq N$).

The next $M$ lines each contain three integers, $u$, $v$, and $s$, where: $u$ and $v$ indicate a bidirectional communication link between base $u$ and base $v$, and $s$ is the score of the communication link ($1 \leq u, v \leq N$ and $0 \leq s \leq 10^5$). There will be at most one link between any two pairs of bases.

Output

The output consists of one integer $T$, the minimum threshold such that there are exactly $K$ connected components of bases. If no threshold, $T$, allows the graph to be partitioned into exactly $K$ connected components, output IMPOSSIBLE.

5 4 3
1 2 6
2 3 4
3 4 8
4 5 10

7

8 7 4
1 2 6
2 3 5
3 4 8
4 5 10
6 8 30
7 1 2
7 8 2

6