题目描述

输入一个 $n$ 个节点，$n-1$ 条无向边的连通图。第 $i$ 条边的起点、终点、权值（长度）分别为 $u_i$、$v_i$、$w_i$。定义图上两点间的距离为，不走重复的边的情况下的路径中所有边的权值（长度）之和。

请问图中距离最近（路径长度最小）的两个不同的点之间的距离是多少?

输入格式

输入第一行为一个整数 $n$，表示有 $n$ 个点，点的编号为 $1\sim n$。

接下来有 $n-1$ 行，第 $i$ 行为空格隔开的 $u_i$、$v_i$、$w_i$。

输出格式

输出一行，为一个整数，即最近点对的距离。

样例

5
1 2 1
1 3 -4
2 4 -3
2 5 -2

-6

样例 1 说明

$3\sim 4$ 距离最近

     1
   1/ \-4
   2   3
-3/ \-2 
 4   5

数据范围

对于 $60\%$ 的数据：$1\le n \le 10$；

对于 $100\%$ 的数据：$1\le n \le 1000$，$1\le u_i,v_i \le n$，$-10^3\le w_i \le 10^3$。