Маленькая девочка Сьюзи случайно нашла тетрадь своего старшего брата. У неё есть много более важных дел, чем решение задач, но эта показалась ей слишком интересной, так что она всё же захотела узнать её решение и решила спросить у вас. Итак, условие задачи.
Пусть дан связный взвешенный неориентированный граф G = (V, E) (здесь V — множество вершин, E — множество рёбер). Деревом кратчайших путей из вершины u называется граф G1 = (V, E1), который является деревом, множество его рёбер E1 является подмножеством множества рёбер исходного графа E, и длины кратчайших путей от u до любой вершины в G и в G1 совпадают.
Вам дан связный взвешенный неориентированный граф G и вершина u. Необходимо найти дерево кратчайших путей заданого графа из вершины u, суммарный вес рёбер которого минимален.
В первой строке находятся два числа n и m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — количество вершин и рёбер графа соответственно.
В следующих m строках находятся по три числа, обозначающих очередное ребро — ui, vi, wi — номера вершин, соединённых ребром, и вес ребра (ui ≠ vi, 1 ≤ wi ≤ 109). Гарантируется, что граф связен, и что между каждой парой вершин существует не более одного ребра.
В последней строке ввода находится целое число u (1 ≤ u ≤ n) — номер стартовой вершины.
Выведите в первой строке минимальный суммарный вес рёбер дерева.
В следующей строке выведите номера рёбер, входящих в дерево, разделяя их пробелом. Рёбра нумеруются с единицы в порядке следования во входных данных. Номера рёбер можно выводить в любом порядке.
Если возможных ответов несколько, выведите любой.
3 3
1 2 1
2 3 1
1 3 2
3
2
1 2
4 4
1 2 1
2 3 1
3 4 1
4 1 2
4
4
2 3 4
В первом тесте из условия возможны два дерева кратчайших путей:
А, например, дерево с ребрами 1 – 2 и 1 – 3 не будет деревом кратчайших путей для вершины 3, потому что расстояние от вершины 3 до вершины 2 в этом дереве равно 3, а в исходном графе оно 1.
| Codeforces Round 303 (Div. 2) |
|---|
| Закончено |
