题目描述(ID:12194)
标题: 甘草危机
标签: 图结构
详情: 牛们干草要用完了!贝茜打算去勘查灾情.
有N(2≤N≤2000)个农场,M(≤M≤10000)条双向道路连接着它们,长度不超过109.每一个农场均与农场1连通.贝茜要走遍每一个农场.她每走一单位长的路,就要消耗一单位的水.从一个农场走到另一个农场,她就要带上数量上等于路长的水.请帮她确定最小的水箱容量.也就是说,确定某一种方案,使走遍所有农场通过的最长道路的长度最小,必要时她可以走回头路.
输入格式:
第1行输入两个整数N和M;接下来M行,每行输入三个整数,表示一条道路的起点终点和长度.
输出格式:
输出一个整数,表示在路线上最长道路的最小值.
样例:

输入

3 3
1 2 23
2 3 1000
1 3 43

输出

43

解释

由1到达2,需要经过长度23的道路;回到1再到3,通过长度43的道路.最长道路为43
登录并解答