Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии Дополнительные ограничения на \(m\) отсутствуют. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Недавно преподавателям «Т-поколения» нужно было сделать учебный контест. Им не хватает одной задачи, и в контесте как раз нет ни одной задачи на графы, поэтому они придумали следующую задачу.
Вам дан связный взвешенный неориентированный граф из \(n\) вершин и \(m\) ребер, который не содержит петель и кратных ребер.
Есть \(q\) вопросов вида \((a, b, k)\): среди всех путей от вершины \(a\) до вершины \(b\) найти наименьший \(k\)-й максимум весов ребер на пути\(^{\dagger}\).
Преподавателям показалось, что задача звучит очень интересно, но есть одно но... они не умеют ее решать. Помогите им и решите задачу, ведь до начала контеста осталось всего пару часов.
\(^{\dagger}\) Пусть \(w_1 \ge w_2 \ge \ldots \ge w_{h}\) — веса всех ребер на пути в порядке невозрастания. Тогда \(k\)-й максимум весов ребер на этом пути равен \(w_{k}\).
Выходные данные
Для каждого набора входных данных выведите ответы на все вопросы.
Примечание
В первом наборе входных данных одним из оптимальных путей в первом запросе является путь \(1 \rightarrow 3 \rightarrow 4\), \(2\)-й максимум весов ребер на этом пути это \(1\). Во втором запросе одними из оптимальных путей являются путь \(2 \rightarrow 4 \rightarrow 3\), \(1\)-й максимум весов ребер это \(2\).
Во втором наборе входных данных одним из оптимальных путей в первом запросе является путь \(1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6\), \(3\)-й максимум весов ребер на этом пути это \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 4 2
1 2 2
2 4 2
1 3 4
3 4 1
1 4 2
2 3 1
6 7 3
1 2 10
2 3 3
3 4 9
4 5 2
5 6 1
2 4 10
4 6 10
1 6 3
1 6 2
2 4 1
11 17 10
1 4 5
1 3 19
1 2 10
3 2 13
4 5 1
4 6 11
3 5 9
3 6 18
2 7 17
5 8 15
5 10 8
6 9 4
7 10 20
7 8 16
8 11 3
9 11 6
10 11 14
3 11 1
3 11 3
1 11 1
1 11 4
1 11 3
8 2 2
10 4 1
3 9 2
3 9 1
6 7 3
|
1 2
2 9 9
11 3 11 1 3 10 8 4 11 4
|