#2182. [Spoj1479]The GbAaY Kingdom最小直径生成树

题目描述

Jiajia is the king of the GbAaY Kingdom. He always squeezes his 20 ministers as coolies. There are n cities and m two-way roads connecting cities in the kingdom. Because of the increasing of the oil fee, he want to simplify the road system in the GbAaY Kingdom to save the traffic cost. Thus, some of roads will be removed. But he requests the ministers guarantee that there is always a path between any two cities. GbAaY Minister Loner suggests Jiajia for the convenience of the traffic management, the farthest distance between cities should be minimal. Unhesitatingly, Jiajia agrees this resolution. As the GbAaY Kingdom's minister (cooly), you must work hard for Jiajia to make the simplification plan. JiaJia是GbAaY王国的王（高贵ING……） 他每天都要挤出20分钟用在做菜上面。 他的王国有N个城市，由M条双向边所连接着。 因为石油的价格上涨，他想把GbAaY王国的交通简化，好节约交通花费。 于是，有些路径需要被移除 但是依然保证移除之后依然有路径连接任意两个城市。 GbAaY的大臣Loner建议JiaJia，为了使交通管理的方便， 整个城市中最长的一条路径需要他的值最小 JiaJia迅速答应了大臣的这个决定。 你作为GbAaY王国的一个大臣，你必须帮助JiaJia简化这个问题

输入格式

The first line contains two integers n, m (1 <= n <= 200, n - 1 <= m <= 50000). Each line of the following m lines contains three integers u, v, w (u != v, 0 <= w <= 10^5). They denote there is a road with length w between city u and city v.

第一行有两个正整数N M(1 <= n <= 200, n - 1 <= m <= 50000). 接着M行每行三个正整数 u,v,w (u != v, 0 <= w <= 10^5) 描述一条连接u,v的双向边的长度是w

输出格式

The first line contains one integer which is the farthest distance between cities after the simplification. 输出第一行有一个正整数表示在简化交通后最远的两个城市的距离

样例

样例输入

3 3  

1 2 1  

2 3 1  

1 3 1  

样例输出

2

数据范围与提示