[Usaco2010 Mar]gather 奶牛大集会

时间限制:1s      空间限制:64MB

题目描述

Bessie正在计划一年一度的奶牛大集会,来自全国各地的奶牛将来参加这一次集会。当然,她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1<=n<=100,000) 1="" 个农场中的一个,这些农场由n-1条道路连接,并且从任意一个农场都能够到达另外一个农场。道路i连接农场a_i和b_i(1="" <="A_i" 考虑一个由五个农场组成的国家,分别由长度各异的道路连接起来。在所有农场中,3号和4号没有奶牛居住。=""


输入格式

第一行:一个整数N * 第二到N+1行:第i+1行有一个整数C_i * 第N+2行到2*N行,第i+N+1行为3个整数:A_i,B_i和L_i。


输出格式

* 第一行:一个值,表示最小的不方便值。


样例输入

5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3

样例输出

15

提示

没有写明提示


题目来源

Gold

Menuappsclose