#D2018. 最近点对

最近点对

题目描述

输入一个 nn 个节点,n1n-1 条无向边的连通图。第 ii 条边的起点、终点、权值(长度)分别为 uiu_iviv_iwiw_i。定义图上两点间的距离为,不走重复的边的情况下的路径中所有边的权值(长度)之和。

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

输入格式

输入第一行为一个整数 nn,表示有 nn 个点,点的编号为 1n1\sim n

接下来有 n1n-1 行,第 ii 行为空格隔开的 uiu_iviv_iwiw_i

输出格式

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

样例

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

样例 1 说明

343\sim 4 距离最近

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

数据范围

对于 60%60\% 的数据:1n101\le n \le 10

对于 100%100\% 的数据:1n10001\le n \le 10001ui,vin1\le u_i,v_i \le n103wi103-10^3\le w_i \le 10^3