4458 . 探險之路
Description
小龍在家裡宅了許久之後，終於決定出去走走了!
他來到了一個秘境，總共有$n$個景點可以去探訪，而景點間總共有$m$條路徑可以走，每一條路經過都需要花費$k$元，花費過一次之後，重覆再走這條路就不用花錢了。小龍很想要每一個景點都看過一次，可是最近買太多遊戲所以快要沒錢了!所以他希望能夠在最少花費的情況下探訪所有的景點，你可以幫他處理這個問題嗎?
Input Format
第一行輸入兩個正整數$n(2 \leq n \leq 4000),m(n-1 \leq m \leq \frac {n(n-1)}{2})$代表景點數和路徑數量。
接下來$m$行每行有$a,b,k(1 \leq k \leq 2147483647)$ 代表從$a$景點到$b$景點需要花費$k$元。
Output Format
請輸出經過所有景點的最小花費。
Sample Input 1
3 3
1 2 3
1 3 2
2 3 1
1 2 3
1 3 2
2 3 1
Sample Output 1
3
Hints
可能會需要在程式前面加ios_base::sync_with_stdio(false);cin.tie(0) 才會過喔!
Subtasks
| No. | Testdata Range | Score |
|---|
