OI Island Traffic System

OI island is a beautiful island with n tourist attractions numbered from \(1\) to \(n\). Recently developed, the island suffers from poor transportation. The OIER Association has been formed to build an efficient road network connecting these attractions. Roads come in two types: level‑1 roads (fast but expensive) and level‑2 roads (slower but cheaper).

The Association plans to construct exactly \(n-1\) roads, forming a spanning tree. In order to ensure efficiency, at least \(k\) of these roads must be level‑1 roads (where \(0 \le k \le n-1\)). Moreover, they wish to keep the cost under control by minimizing the cost of the most expensive road used in the construction. Given a list of possible roads that can be built, your task is to choose \(n-1\) roads satisfying the conditions so that the maximum road cost is as small as possible. If it is impossible to meet the requirements, output \(-1\).

Input format:

• The first line contains three integers: \(n\), \(m\), and \(k\) — the number of attractions, the number of candidate roads, and the minimum required number of level‑1 roads, respectively.
• Each of the next \(m\) lines contains four integers \(u\), \(v\), \(t\), and \(c\), which denote a candidate road connecting attractions \(u\) and \(v\) with type \(t\) and cost \(c\). Here, \(t = 1\) represents a level‑1 road and \(t = 2\) represents a level‑2 road.

Output format:

• Output a single integer representing the minimized maximum cost among the selected roads if such a selection exists; otherwise, output \(-1\).

Note: A solution, if it exists, is guaranteed to have exactly \(n-1\) roads connecting all attractions, and at least \(k\) of them are level‑1 roads.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\). Each of the following \(m\) lines contains four integers \(u\), \(v\), \(t\), and \(c\), representing a candidate road.

Example:

3 3 1
1 2 1 5
2 3 2 3
1 3 1 7

outputFormat

A single integer denoting the minimized maximum cost among the roads in a spanning tree that includes at least \(k\) level‑1 roads. If no valid spanning tree exists under the given conditions, output \(-1\).

sample

3 3 1
1 2 1 5
2 3 2 3
1 3 1 7

5