BubbleLand里的人喜欢喝啤酒。你却不知道,这里的啤酒是如此的醇厚,以至于你每次喝下它的时候,你的速度都会比喝之前慢10倍。
Birko 住在贝尔格莱德市,但想去贝尔堡市。你有一张BubbleLand的路线图,你需要为他找到最快的路线。当他在贝尔格莱德开始旅程时,他的速度是 1。当他来到一个新城市时,他总是尝试一杯当地的啤酒,这会将他的速度除以 10。
这里的问题是他到达啤酒堡的最短时间是多少。如果有多条路径的最短时间相同,请选择其中道路最少的一条。如果仍有多条路径,请选择任意一条。
保证至少有一条从 Beergrade 到 Beerburg 的路径。
输入
输入的第一行包含整数 N — Bubbleland 中的城市数量和整数 M — 该国家/地区的道路数量。城市从0到N-1进行枚举,其中城市0是Beergrade,城市N-1是Beerburg。接下来的M行每一行都包含三个整数a、b(a≠b)和len。这些数字表明城市 a 和 b 之间有一条长度为 len 的双向道路。
- 2 ≤ N ≤ 105
- 1 ≤ M ≤ 105
- 0 ≤ len ≤ 9
- 两个城市之间最多只有一条路
输出
输出的第一行应包含从 Beergrade 到 Beerburg 所需的最短时间。
输出的第二行应包含从 Beergrade 到 Beerburg 所需时间最短的路径上的城市数量。
输出的第三行应包含此路径上城市的数量(按访问顺序排列),并用空格分隔。
示例
输入 #1
8 10 0 1 1 1 2 5 2 7 6 0 3 2 3 7 3 0 4 0 4 5 0 5 7 2 0 6 0 6 7 7
输出 #1
32 3 0 3 7