Description

下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

如图：求v1到v10的最短路径长度及最短路径。

Input Format

输入第一行为一个数n（n<=12），表示节点个数

接下来n行每行有n个数，表示n个节点的邻接矩阵

Output Format

输入包含两行，第一行是一个数，表示最短路径的长度，第二行分别输出最短路径上的节点。

7
0 3 5 0 0 0 0
0 0 0 7 8 6 0
0 0 0 0 4 5 0
0 0 0 0 0 0 4
0 0 0 0 0 0 7
0 0 0 0 0 0 6
0 0 0 0 0 0 0

minlong=14
1 2 4 7