E. Пути и деревья
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленькая девочка Сьюзи случайно нашла тетрадь своего старшего брата. У неё есть много более важных дел, чем решение задач, но эта показалась ей слишком интересной, так что она всё же захотела узнать её решение и решила спросить у вас. Итак, условие задачи.

Пусть дан связный взвешенный неориентированный граф 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 – 3 и 2 – 3 (суммарный вес 3);
  • с ребрами 1 – 2 и 2 – 3 (суммарный вес 2);

А, например, дерево с ребрами 1 – 2 и 1 – 3 не будет деревом кратчайших путей для вершины 3, потому что расстояние от вершины 3 до вершины 2 в этом дереве равно 3, а в исходном графе оно 1.