CSES1203 访问城市
#CS1203. 访问城市
访问城市
题目背景
翻译自 CSES-1203 题。
题目描述
你想从Syrjälä城市通过飞机以最低价格的路线前往Lehmälä城市。你需要确定你一定会经过哪些城市？
输入格式
第一行包含两个整数 n 和 m：分别表示城市的数量和航班的数量。城市编号为 1,2,…,n1, 2, \dots, n1,2,…,n，其中城市 1 是Syrjälä，城市 n 是Lehmälä。
接下来有 m 行，每行包含三个整数 a、b 和 c，表示有一条从城市 a 到城市 b 的航班，票价为 c。所有航班都是单向的。
你可以假设从Syrjälä到Lehmälä一定存在一条路径。
输出格式
首先输出一个整数 k：表示必定会经过的城市数量。然后，输出这 k 个城市，按升序排列。
样例
5 6
1 2 3
1 3 4
2 3 1
2 4 5
3 4 1
4 5 8
4
1 3 4 5
说明/提示