A5037 | $午枫的双向奔赴$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

AC国有 $n$ 座城市，这些城市由城市交通系统联系在一起，城市交通系统由 $m$ 条道路组成，每条道路连接两座城市 $u$ 和 $v$ ，通过这条道路需要花费 $t$ 时间，且从某座城市出发都可以到达任意一座城市。 小午位于 $1$ 号城市，小枫位于 $n$ 号城市，他们想在某座城市会和，求他们会和需要的最短时间以及以最短时间能到达的所有城市编号，按照编号从小到大输出。

第一行输入两个正整数 $n,m$ $(1\leq n\leq 2\times 10^5,n-1\leq m \leq2\times 10^5)$ ，分别表示城市数量和道路数量。 接下来 $m$ 行，每行输入三个正整数 $u,v,t$ $(1\leq u\lt v\leq n,1\leq t \leq 10^9)$ ，表示一条道路连接的两个城市，以及通过这条道路需要花费的时间。

输出包含两行。 第一行输出一个整数 $cost$ ，表示小午和小枫会和的最短时间。 第二行输出若干整数，表示花费最短时间可以会和的城市编号，如果有多座城市，按照城市编号从小到大输出。

输入 #1

输出 #1

3
3

C++ 编辑器

输入

输出