题目描述

为了联合对抗天顶星人的入侵,魔法世界的各个大城市之间建设了许多能量传送带.如 图所示,

共有$\red{10}$个城市$\red{V_1,...,V_{10}}$。,起点是$\red{V_1,}$终点是$\red{V_{10},}$每个城市之间的能量传 送带是单向的,例如: $\red{V_1}$到$\red{V_2}$的距离是$\red{2,V_1}$到$\red{V_3}$的距离是$\red{5,...,}$请编程求出$\red{V_1}$到$\red{V_{10}}$ 的最短路径长度。

输入格式

第一行为$\red{N,}$表示有$\red{N(N<100)}$个城市,以下每行有三个数字$\red{a,b,c,}$表示从第$\red{a}$城市. 到第$\red{h}$城市的距离为$\red{c，}$最后一行以$\red{0~0~0}$结束.

输出格式

输出一个整数,即从城市$\red{1}$到城市$\red{N}$的最短路径。

样例

输入样例

3
1 2 2
2 3 5
0 0 0

输出样例

7