Preparing NOJ

公路建设

1000ms 65536K

Description:

L的公司要为n个村子之间建立公路,使任意两个村子之间都能直接或间接进行访问。由于村子之间的公路建设都需要一定的费用,L想这些修路的总费用达到最小值。当L设计出修路方案时,L的上级却下令L要设计出另外一套方案,同时也使得费用尽量的小,简称为次小费用方案。那么,你能帮L实现这个次小费用方案吗?

Input:

第一行有两个正整数nm(n<1000m<=498501)n表示村子的个数,m表示公路的信息个数。

接下来有m 行,每一行有三个正整数 x y c (0<c<=100)表示修建村子x和村子y之间的铁路需要费用c

数据保证存在最小费用和次小费用的设计方案。

Output:

输出一个正整数,表示次小费用的值。

Sample Input:

3 3
1 2 1
2 3 2
3 1 3

Sample Output:

4

Note:

 

本题由旧版NOJ导入,来源:李鸿斌(honghu)

Info

NOJ

Provider NOJ

Code NOJ1188

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet