CF575G.Run for beer

People in BubbleLand like to drink beer. Little do you know, beer here is so good and strong that every time you drink it your speed goes 10 times slower than before you drank it.

Birko lives in city Beergrade, but wants to go to city Beerburg. You are given a road map of BubbleLand and you need to find the fastest way for him. When he starts his journey in Beergrade his speed is 1. When he comes to a new city he always tries a glass of local beer, which divides his speed by 10.

The question here is what the minimal time for him to reach Beerburg is. If there are several paths with the same minimal time, pick the one that has least roads on it. If there is still more than one path, pick any.

It is guaranteed that there will be at least one path from Beergrade to Beerburg.

BubbleLand 的人们喜欢喝啤酒。鲜为人知的是，这里的啤酒品质极佳且劲道十足——每次饮用后，你的移动速度都会变为饮酒前的十分之一。

Birko 居住在 Beergrade 城市，但想去 Beerburg 城市。现给你一张 BubbleLand 的道路地图，你需要为他找出最快捷的路径。他在 Beergrade 出发时的初始速度为 $1$；每当他抵达一座新城市时，总会品尝一杯当地的啤酒，使其速度除以 $10$。

本题要求：计算他到达 Beerburg 所需的最短时间。若存在多条路径具有相同的最短时间，则选择其中边数最少的一条；若仍存在多条满足条件的路径，则任选其一即可。

题目保证：从 Beergrade 到 Beerburg 至少存在一条路径。

The first line of input contains integer N — the number of cities in Bubbleland and integer M — the number of roads in this country. Cities are enumerated from 0 to N - 1, with city 0 being Beergrade, and city N - 1 being Beerburg. Each of the following M lines contains three integers a, b (a ≠ b) and len. These numbers indicate that there is a bidirectional road between cities a and b with length len.

• 2 ≤ N ≤ 105
• 1 ≤ M ≤ 105
• 0 ≤ len ≤ 9
• There is at most one road between two cities

输入的第一行包含两个整数 $N$（Bubbleland 国家的城市数量）和 $M$（该国的道路数量）。城市编号从 $0$ 到 $N-1$，其中城市 $0$ 为 Beergrade，城市 $N-1$ 为 Beerburg。接下来的 $M$ 行每行包含三个整数 $a$、$b$（$a \ne b$）和 $len$，表示在城市 $a$ 与城市 $b$ 之间存在一条长度为 $len$ 的双向道路。

• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $0 \le len \le 9$
• 任意两座城市之间至多存在一条道路

The first line of output should contain minimal time needed to go from Beergrade to Beerburg.

The second line of the output should contain the number of cities on the path from Beergrade to Beerburg that takes minimal time.

The third line of output should contain the numbers of cities on this path in the order they are visited, separated by spaces.

第一行输出应包含从 Beergrade 到 Beerburg 所需的最少时间。

第二行输出应包含从 Beergrade 到 Beerburg 的、耗时最少的路径所经过的城市数量。

第三行输出应包含该路径上按访问顺序排列的城市编号，各编号之间用空格分隔。