Вам задан связный неориентированный взвешенный граф, состоящий из \(n\) вершин и \(m\) ребер.
Вам необходимо вывести \(k\)-й минимальный кратчайший путь в этом графе (пути из вершины в саму себя не учитываются, пути из вершины \(i\) в вершину \(j\) и из вершины \(j\) в вершину \(i\) считаются за один).
Более формально, если \(d\) — матрица кратчайших путей, где \(d_{i, j}\) равно длине кратчайшего пути между вершинами \(i\) и \(j\) (\(1 \le i < j \le n\)), то вам необходимо вывести \(k\)-й элемент в отсортированном массиве, состоящем из всех \(d_{i, j}\), где \(1 \le i < j \le n\).
Выходные данные
Выведите одно целое число — длину \(k\)-го минимального кратчайшего пути в заданном графе (пути из вершины в саму себя не учитываются, пути из вершины \(i\) в вершину \(j\) и из вершины \(j\) в вершину \(i\) считаются за один).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 10 5
2 5 1
5 3 9
6 2 2
1 3 1
5 1 8
6 5 10
1 6 5
6 4 6
3 6 2
3 4 5
|
3
|
|
2
|
7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1
|
9
|