Дан взвешенный неориентированный граф из n вершин и m ребер. Найдите кратчайший путь из вершины s в вершину t, либо определите, что пути не существует.
Выходные данные
В первой строке выведите остаток от деления длины кратчайшего пути на 1000000007 (109 + 7), если путь существует, и -1, если пути не существует.
В случае, если путь существует, во второй строке выведите целое число k —количество вершин в кратчайшем пути из вершины s в вершину t; в третьей строке выведите k чисел, разделенных пробелами — вершины кратчайшего пути в порядке посещения. Первая вершина должна быть вершиной s, последняя — вершиной t. Если существует несколько кратчайших путей, выведите любой.
Примечание
Путем из вершины s в вершину t называется последовательность вершин v0, ..., vk, такая что v0 = s, vk = t, и для любого i от 0 до k - 1 вершины vi и vi + 1 соединены ребром.
Длиной пути называется сумма длин ребер между vi и vi + 1 для всех i от 0 до k - 1.
Кратчайшим путем из s в t называется путь, длина которого минимальна среди всех возможных путей из s в t.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 4 2
1 2 0
2 3 0
3 4 0
1 4
|
3
4
1 2 3 4
|
|
2
|
4 3
1 2 4
2 3 5
3 4 6
1 4
|
112
4
1 2 3 4
|
|
3
|
4 2
1 2 0
3 4 1
1 4
|
-1
|