题目描述

有 $N$ 个城市，编号为 $1$ 到 $N$。给定城市之间的单向道路及每条道路的费用，请求出从城市 $1$ 到城市 $N$ 的最短路径长度，并输出一条对应的最短路径。

输入格式

第一行包含一个整数 $N$，表示城市数量。

接下来 $N$ 行，每行包含 $N$ 个整数。第 $i$ 行第 $j$ 个整数表示从城市 $i$ 到城市 $j$ 的道路费用；若该数为 $0$，表示两座城市之间没有这条单向道路。

输出格式

第一行输出从城市 $1$ 到城市 $N$ 的最短路径长度。

第二行依次输出最短路径经过的城市编号，编号之间用空格分隔。

样例

10
0 2 5 1 0 0 0 0 0 0
0 0 0 0 12 14 0 0 0 0
0 0 0 0 6 10 4 0 0 0
0 0 0 0 13 12 11 0 0 0
0 0 0 0 0 0 0 3 9 0
0 0 0 0 0 0 0 6 5 0
0 0 0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0

19
1 3 5 8 10

数据范围与提示

• 输入保证城市 $1$ 可以到达城市 $N$。