题目描述

各个大城市之间铺设了许多道路，如下图所示，共有10个城市V1，…，V10​，起点是V1，终点是V10​，每个城市之间的道路是单向的，例如：V1到V2的距离是2，V1到V3的距离是5……，请编程求出$V_1$到$V_n$的最短路径长度。

输入格式

第一行为N，表示有N（N＜100）个城市，以下每行有三个数字a，b，c，表示从第a城市到第b城市的距离为c。

最后一行以 0 0 0 结束。

输出格式

输出一个整数，即从城市1到城市N的最短路径。

3
1 2 2
2 3 5
0 0 0

7