F. K-th Path
brute force; constructive algorithms; shortest paths; sortings
You are given a connected undirected weighted graph consisting of \(n\) vertices and \(m\) edges.You need to print the \(k\)-th smallest shortest path in this graph (paths from the vertex to itself are not counted, paths from \(i\) to \(j\) and from \(j\) to \(i\) are counted as one).More formally, if \(d\) is the matrix of shortest paths, where \(d_{i, j}\) is the length of the shortest path between vertices \(i\) and \(j\) (\(1 \le i < j \le n\)), then you need to print the \(k\)-th element in the sorted array consisting of all \(d_{i, j}\), where \(1 \le i < j \le n\).
The first line of the input contains three integers \(n, m\) and \(k\) (\(2 \le n \le 2 \cdot 10^5\), \(n - 1 \le m \le \min\Big(\frac{n(n-1)}{2}, 2 \cdot 10^5\Big)\), \(1 \le k \le \min\Big(\frac{n(n-1)}{2}, 400\Big)\) — the number of vertices in the graph, the number of edges in the graph and the value of \(k\), correspondingly.Then \(m\) lines follow, each containing three integers \(x\), \(y\) and \(w\) (\(1 \le x, y \le n\), \(1 \le w \le 10^9\), \(x \ne y\)) denoting an edge between vertices \(x\) and \(y\) of weight \(w\).It is guaranteed that the given graph is connected (there is a path between any pair of vertices), there are no self-loops (edges connecting the vertex with itself) and multiple edges (for each pair of vertices \(x\) and \(y\), there is at most one edge between this pair of vertices in the graph).
Print one integer — the length of the \(k\)-th smallest shortest path in the given graph (paths from the vertex to itself are not counted, paths from \(i\) to \(j\) and from \(j\) to \(i\) are counted as one).