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

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

Формат входных данных

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

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

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

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

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

Формат результата

В ответ выведите три строки.

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

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

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

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

Salekhova58    1   11.11.2021 02:27    4