题目描述

有 $n$ 座城市，编号为 $1$ 到 $n$。道路都是单向的，且只从编号小的城市通向编号大的城市。求从城市 $1$ 到城市 $n$ 的最少费用，并输出一条费用最少的路线。

输入格式

第一行一个整数 $n$。接下来 $n$ 行，每行 $n$ 个整数，构成邻接矩阵。正整数表示道路费用，$0$ 表示没有道路。

输出格式

第一行输出 minlong=最少费用。第二行按顺序输出路线上的城市编号，用空格分隔。存在多条最优路线时输出任意一条。

样例

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

minlong=19
1 3 5 8 10

数据范围

$1\le n\le100$，道路费用不超过 $1000000$。保证从 $1$ 可以到达 $n$。