海蒂的朋友珍妮要求海蒂向他们共同的朋友之一转递一封重要的信。由于珍妮是爱尔兰人,海蒂认为这可能是一个恶作剧。更准确地说,她怀疑她被要求传递的消息是:“让傻瓜走得更远!”,并且在阅读该消息后,接收者会要求海蒂将相同的消息传递给另一个朋友(接收者与海蒂有共同点),等等。
海蒂认为她的朋友们想避免尴尬的情况,所以她不会被要求去拜访同一个人(包括珍妮)两次。她还知道任意两个互相认识的朋友之间的旅行费用是多少。她想知道:如果这真的是一个恶作剧,她最多会在旅行上浪费多少钱?
海蒂的 n 好友被标记为 0 通过 n - 1,他们的连接网络形成一棵树。换句话说,她的每两个朋友 a, b 彼此认识,可能是间接的(有一系列朋友从 a 并结束于 b 并且使得序列中的每两个连续的朋友直接互相认识),并且正好有 n - 1 一对直接认识的朋友。
珍妮得到了号码 0.
输入
第一行输入包含好友数量 n (3 ≤ n ≤ 100)。下一个 n - 1 行每行包含三个空格分隔的整数 u, v 和 c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104),这意味着 u 和 v 是朋友(直接认识)以及之间的交通费用 u 和 v is c.
保证输入的社交网络形成一棵树。
输出
输出一个整数——成本的最大总和。
示例
输入复制
4
0 1 4
0 2 2
2 3 3
输出复制
5
输入复制
6
1 2 3
0 2 100
1 4 2
0 3 7
3 5 10
输出复制
105
输入复制
11
1 0 1664
2 0 881
3 2 4670
4 2 1555
5 1 1870
6 2 1265
7 2 288
8 7 2266
9 2 1536
10 6 3378
输出复制
5551
注意
在第二个示例中,最坏的情况是这样的:Jenny 将 Heidi 发送给号码标记的朋友 2 (产生的费用为 100),那么朋友 2 将她发送给朋友 1 (成本海蒂 3),最后是朋友 1 将她转发给朋友 4 (产生额外费用 2).