Утренняя подработка

Сдать решение задачи B-Утренняя подработка
Полный балл: 100
Бонусные баллы:
Имя входного файла: in.txt или стандартный поток ввода
Имя выходного файла: out.txt или стандартный поток вывода
Ограничение времени: 1500 мс
Ограничение памяти: 256M
Утренняя подработка
Школьник Федя подрабатывает по утрам почтальоном, разнося газеты местным жителям - в каждый дом по одной. А ещё Федя - очень прилежный ученик, так что не любит опаздывать в школу.

К сожалению, сегодня Федя проспал, так что он очень торопится добраться до школы, поэтому пойдёт по самому короткому возможному пути. Но по дороге он хочет разнести как можно больше газет - не оставлять же граждан без утреннего чтива! Помогите Феде - найдите для него оптимальный маршрут с учётом его пожеланий.

Формат входных данных
В первой строке входных данных через пробел заданы два целых числа n - количество домов и m - количество дорог между домами (1 ≤ n, m ≤ 3 × 105).

Во второй строке входных данных через пробел заданы два целых числа s, t (1 ≤ s, t ≤ n, s ≤ t) - номер дома, в котором живёт Федя и дома, где находится его школа.

В последующих m строках через пробел заданы три целых числа a, b, c (1 ≤ a < b ≤ n, 1 ≤ c ≤ 109) - номера домов, соединённых дорогой, и длина дороги. Федя может перемещаться только по дорогам.

Гарантируется, что никакая пара чисел (a, b) не встречается во входных данных два раза.

Также гарантируется, что Федя может добраться от любого дома до любого другого по дорогам.

Формат результата
В ответ выведите три строки.

В первой строке выведите суммарную длину дорог на оптимальном пути Феди.

Во второй строке выведите количество газет, разнесённых Федей (себе домой и в школу Федя газеты не разносит).

В третьей строке выведите через пробел все дома, в которые Федя должен занести газеты, в том же порядке, в котором Федя должен их посетить.

Если существует несколько оптимальных маршрутов, вы можете вывести любой из них.

Примеры
Входные данные
7 10
1 7
1 2 3
1 3 2
1 4 4
2 4 2
2 7 5
3 4 2
3 6 2
4 5 2
5 6 2
5 7 2
Результат работы
8
3
3 4 5
Примечания
В примере существует четыре самых коротких маршрута от дома Феди до школы:

1 → 2 → 7

1 → 4 → 5 → 7

1 → 3 → 6 → 5 → 7

1 → 3 → 4 → 5 → 7

Среди них Федя посетит больше всего домов на третьем и четвёртом маршрутах. В ответ можно вывести любой из них.

Система оценки:

Решения, корректно работающие для n ≤ 10, получат не менее 20 баллов.

Решения, корректно работающие для n, m ≤ 1000, получат не менее 40 баллов.

Решения, корректно работающие для ci = 1, получат не менее 40 баллов.

0

Алгоритм Дейкстры

0