← 返回题目列表

Codeforces · 575/G

G. 跑去喝啤酒

中文机器翻译题面 查看原题

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