Problem D: 广播发送

Problem D: 广播发送

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 65  Solved: 33
[Submit] [Status] [Web Board] [Creator:]

Description



       在著名的cjDD国的首都有个广播发送站,每天都发送着全国的广播,而每座城市里都有一个广播接收塔,负责接收和转发广播!由于各方面的原因,每两个广播之间传播的时间不一样!(对于任意两个广播站无论从谁传向谁时间都是一样的)。

       问一则广播从cjDD国的首都总站开始到全国各地最少需要多少时间(不考虑接收和转发时间,换句话说只考虑,传播时间)。


						

Input


第一行输入一个整数N1N1000)—表示一共有N个城市(1为首都)。

       接下来n-1行第i行有i个数(或者x—表示i+1城市的广播站和他前面编号的城市的广播站的传播时间(1<数≤10000)。x表示这两个城市不能传播。






						

Output

对于每一个样例输出一个整数—表示最少花费的时间。

Sample Input Copy

5
50
30 5
100 20 50
10 x x 10

Sample Output Copy

35