CF575G Run for beer

泡泡国的人们喜欢喝啤酒。你或许不知道，这里的啤酒既美味又烈，以至于每喝一次，速度就会变为之前的 $1/10$。 Birko 住在 Beergrade 城，但他想去 Beerburg 城。现在给定泡泡国的道路地图，你需要帮他找到最快到达目的地的方案。当他从 Beergrade 出发时，速度为 $1$。每当他到达一个新的城市时，他都会品尝当地的啤酒，他的速度会被 $10$ 除。 现在的问题是，从 Beergrade 到 Beerburg 的最短时间是多少。如果存在多条用时相同的路径，请输出经过道路数最少的路径。如果还有多条路径，任选其一即可。 保证从 Beergrade 到 Beerburg 至少存在一条路径。

第一行包含整数 $N$ — 泡泡国的城市数量，以及整数 $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$ - 任意两座城市之间最多有一条道路

输出共三行： 第一行为从 Beergrade 到 Beerburg 的最短所需时间。 第二行为在该路径上经过的城市数目。 第三行为该路径上按访问顺序排列的城市编号，编号之间用空格隔开。

由 ChatGPT 5 翻译