CF1196F K-th Path

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).