题目描述

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

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

输入格式

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

输出格式

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

样例

输入样例

3
1 2 2
2 3 5
0 0 0

输出样例

7