第三帝國

題目敘述

為了雅利安人的榮耀，元首決定在統一歐洲後建立以慕尼黑為中心的第三帝國。假設當時歐洲有$N$個城市，有$M$條道路連接這些城市，為了管理方便，希望每個城市都可以有一條路徑通往首都，但是因為打仗的關係所有道路都斷了，因此他要求身為工程師的你進行道路修復。每條路修復的費用都不一樣，為了節省國庫，你希望能花越少的費用越好，請你向元首會報你最少需要多少馬克。

輸入說明

第一行有兩個數字$N,M$表示有$N$城市，$M$條損毀的道路，城市的編號為$0,1,2,...,N-1$，編號0號為首都。接下來有$M$行，每行有三個正整數(int)$A,B,C$表示$A$城市和$B$城市間有一條損毀的道路，要修復他要花費$C$馬克。

輸出說明

如果沒辦法讓所有城市和首都連通，請輸出Und doch habe ich allein，不然輸出最少需要多少馬克才能讓所有城市和首都連通。

範例輸入1

4 5
0 1 5
0 2 3
2 3 2
2 1 4
3 0 1

範例輸出1

7

範例輸入2

5 5
0 1 2
1 3 5
2 4 6
3 0 9
4 2 8

範例輸出2

Und doch habe ich allein

配分方法

• 30% $1 \leq N \leq 1000$
• 70% $1 \leq N \leq 100000$
• 100% $0 \leq M \leq 1000000$

Hints

備註

Judge Setting