给定一个有 n 个顶点和 m 个边的加权无向图。找到从顶点 s 到顶点 t 的最短路径,否则说明该路径不存在。
输入
输入的第一行包含两个空格分隔的整数 — n 和 m (1 ≤ n ≤ 105;0 ≤ m ≤ 105)。
接下来的 m 行包含图边的描述。第 i 行包含三个以空格分隔的整数 — ui、vi、xi (1 ≤ ui, vi ≤ n; 0 ≤ xi ≤ 105)。这意味着编号为 ui 和 vi 的顶点通过长度为 2xi(2 的 xi 次方)的边连接。
最后一行包含两个空格分隔的整数 - 顶点 s 和 t 的数量。
顶点编号为 1 到 n。该图不包含重边和自环。
输出
在第一行中,如果路径存在,则打印最短路径的长度除以 1000000007 (109 + 7) 后的余数,如果路径不存在,则打印 -1。
如果路径存在则在第二行打印整数 k — 从顶点 s 到顶点 t 的最短路径中的顶点数;第三行打印 k 个空格分隔的整数——访问顺序中最短路径的顶点。第一个顶点应该是顶点 s,最后一个顶点应该是顶点 t。如果有多个最短路径,则打印其中任意一个。
示例
输入 #1
4 4 1 4 2 1 2 0 2 3 0 3 4 0 1 4
输出 #1
3 4 1 2 3 4
输入 #2
4 3 1 2 4 2 3 5 3 4 6 1 4
输出 #2
112 4 1 2 3 4
输入 #3
4 2 1 2 0 3 4 1 1 4
输出 #3
-1
注意
从顶点 s 到顶点 t 的路径是序列 v0, ..., vk,使得 v0 = s, vk = t,并且对于从 0 到 k - 1 的任何 i,顶点 vi 和 vi + 1 通过边连接。
路径的长度是对于从 0 到 k - 1 的所有 i,vi 和 vi + 1 之间的边的权重之和。
从s到t的最短路径是从s到t的所有可能路径中长度最小的路径。