Маленькая девочка Сьюзи случайно нашла тетрадь своего старшего брата. У неё есть много более важных дел, чем решение задач, но эта показалась ей слишком интересной, так что она всё же захотела узнать её решение и решила спросить у вас. Итак, условие задачи.
Пусть дан связный взвешенный неориентированный граф G = (V, E) (здесь V — множество вершин, E — множество рёбер). Деревом кратчайших путей из вершины u называется граф G1 = (V, E1), который является деревом, множество его рёбер E1 является подмножеством множества рёбер исходного графа E, и длины кратчайших путей от u до любой вершины в G и в G1 совпадают.
Вам дан связный взвешенный неориентированный граф G и вершина u. Необходимо найти дерево кратчайших путей заданого графа из вершины u, суммарный вес рёбер которого минимален.
Выходные данные
Выведите в первой строке минимальный суммарный вес рёбер дерева.
В следующей строке выведите номера рёбер, входящих в дерево, разделяя их пробелом. Рёбра нумеруются с единицы в порядке следования во входных данных. Номера рёбер можно выводить в любом порядке.
Если возможных ответов несколько, выведите любой.
Примечание
В первом тесте из условия возможны два дерева кратчайших путей:
- с ребрами 1 – 3 и 2 – 3 (суммарный вес 3);
- с ребрами 1 – 2 и 2 – 3 (суммарный вес 2);
А, например, дерево с ребрами 1 – 2 и 1 – 3 не будет деревом кратчайших путей для вершины 3, потому что расстояние от вершины 3 до вершины 2 в этом дереве равно 3, а в исходном графе оно 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 1
2 3 1
1 3 2
3
|
2
1 2
|
|
2
|
4 4
1 2 1
2 3 1
3 4 1
4 1 2
4
|
4
2 3 4
|