Spanning Tree with Minimum Maximum Connection Time and At Least K Student Edges

Kiana has taught n distinct knowledge points and prepared m potential connections between pairs of these points. Each connection i can be explained in one of two ways:

• If Kiana teaches it directly, it takes time \(t_i\).
• If the student figures it out by himself, it takes time \(T_i\).

Kiana needs to form a connected structure (i.e. a spanning tree) on the n knowledge points by selecting exactly n-1 out of the m connections. In addition, at least k of the chosen connections must be derived by the student on his own.

For a given connection \(i\), the available modes under a prescribed time limit \(L\) are:

• If \(t_i \le L\) then it is possible to use the teacher mode.
• If \(T_i \le L\) then it is possible to use the student mode.

An edge can be used if at least one mode is available (i.e. if \(\min(t_i, T_i) \le L\)). Moreover, if both modes are available \( (t_i \le L \text{ and } T_i \le L) \), then that connection can be marked as a student‐derived connection if desired. However, if only the teacher mode is available \((t_i \le L \text{ and } T_i > L)\), then it cannot count toward the required k student edges.

Kiana wants to minimize the maximum time used among the selected connections. Formally, she wants to find the smallest \(L\) such that there exists a spanning tree whose every edge \(i\) is used in a mode with time \(\le L\) and at least \(k\) of these edges are used in the student mode (i.e. their \(T_i \le L\)).

If no such spanning tree can be constructed, output -1.

inputFormat

The first line contains three integers n, m, and k (\(2 \le n \le 10^5\), \(n-1 \le m \le 10^5\), \(0 \le k \le n-1\)). Each of the next m lines contains four integers \(u\), \(v\), \(t_i\), and \(T_i\) (\(1 \le u,v \le n, u \neq v, 1 \le t_i, T_i \le 10^9\)), which describe a connection between knowledge points u and v with teacher mode time \(t_i\) and student mode time \(T_i\).

outputFormat

Output a single integer: the minimum possible L such that a spanning tree exists meeting the requirements, or -1 if it is impossible.

sample

3 3 1
1 2 1 2
2 3 2 3
1 3 3 4

2