← 返回题目列表

Codeforces · 802/J1

J1. 让傻瓜走得更远! (简单)

中文机器翻译题面 查看原题

海蒂的朋友珍妮要求海蒂向他们共同的朋友之一转递一封重要的信。由于珍妮是爱尔兰人,海蒂认为这可能是一个恶作剧。更准确地说,她怀疑她被要求传递的消息是:“让傻瓜走得更远!”,并且在阅读该消息后,接收者会要求海蒂将相同的消息传递给另一个朋友(接收者与海蒂有共同点),等等。

海蒂认为她的朋友们想避免尴尬的情况,所以她不会被要求去拜访同一个人(包括珍妮)两次。她还知道任意两个互相认识的朋友之间的旅行费用是多少。她想知道:如果这真的是一个恶作剧,她最多会在旅行上浪费多少钱?

海蒂的 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).