本题没有可用的提交语言。

题目描述

农民约翰正在建造一台新的挤奶机,并希望尽可能长时间地保密。他藏在农场深处,需要能够到达机器而不被发现。他必须在机器建造过程中总共进行$T(1 <= T <= 200)$次。他有一个秘密隧道,他只用于回程。

农场包括$N(2 <= N <= 200)$地标(编号1。N)通过$P(1 <=P <= 40,000)$双向跟踪连接(编号1。P)并且具有不超过$1,000,000$的正长度。多条小径可能会加入一对地标。

为了尽量减少他的检测机会,FJ知道他不能不止一次地在农场使用任何小径,他应该尝试使用最短的小径。

帮助FJ从谷仓(地标1)到秘密挤奶机(landmark N)共$T$次。找到他必须使用的最长单条小径的最小可能长度,但受限制,他使用不超过一次的痕迹。(注意:目标是尽量减少最长小径的长度,而不是小径长度的总和。

保证FJ可以在不重复使用痕迹的情况下进行所有T旅行。

输入

行1:三个空间分隔整数:$N、P和T$

*第2行。$P+1:$行$i+1$包含三个空间分隔的整数,$A_i,B_i$和$L_i,$表明一条小径将地标$A_i$与长度为$L_i$的地标$B_i$连接起来。

输出

*第1行:单个整数,是农民约翰路线最长段的最小可能长度。 输入数 1

7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3

输出数位 1

5

提示

农民约翰可以旅行小径$1 - 2 - 3 - 7$和$1 - 6 - 7$。行驶的步道长度不超过5个单位。农民约翰不可能从1到7两次旅行,而不使用至少一条长度5的步道。

巨大的输入数据,scanf推荐。 来源

USACO 2005年2月黄金