k992. 送外賣2 - 高中生程式解題系統

內容

肯肯肯點了一份外賣，但是竟然沒有路通向他家，於是他一氣之下決定在 $n$ 個城市間建設道路。

總共有 $m$ 個建路的方案，每個方案可以表示成 $a, b, w$ ，代表在城市 $a, b$ 間用 $w$ 的成本建一條路，並且如果把這 $m$ 個方案的路都連起來， $n$ 個城市是可以互相抵達的。

肯肯肯打算建 $n - 1$ 條路連通所有城市，因為他的錢太多了，他想要讓總成本越大越好。

為了花更多錢，肯肯肯可以使選擇其中一個方案，讓這個方案的建路成本變 $5$ 倍。

請問肯肯肯最多可以花多少錢呢？

輸入說明

第一行輸入兩個正整數 $n, m$ 。

接下來 $m$ 行，每行輸入三個正整數 $a, b, w$ 。

$2 \leq n \leq 10^{5}$
$n - 1 \leq m \leq 2 \times 10^{5}$
$1 \leq a < b \leq n$
$1 \leq w \leq 10^{8}$
不會有重複的 $(a, b)$

輸出說明

輸出一個整數代表肯肯肯最多可以花多少錢。

範例輸入 #1

2 1
1 2 100

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 128 MB
不公開測資點#0 (12%): 2.0s , <1K
不公開測資點#1 (12%): 2.0s , <1K
不公開測資點#2 (12%): 2.0s , <10M
不公開測資點#3 (12%): 2.0s , <10M
不公開測資點#4 (13%): 2.0s , <10M
不公開測資點#5 (13%): 2.0s , <10M
不公開測資點#6 (13%): 2.0s , <10M
不公開測資點#7 (13%): 2.0s , <10M

提示：

$100 % ：無特別限制$

標籤:

出處:

第七屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」