mst (mst)

Tempo limite 1 sec.

Descrizione del problema

Si calcoli il minimo albero ricoprente di un grafo pesato non orientato avente N nodi e M archi.

Dati di input

Il file input.txt contiene sulla prima riga N e M, separati da uno spazio. Le successive M righe contengono tre numeri interi positivi, u, v, w, che rappresentano un arco di peso w che collega i nodi u e v (numerati da 1 a N).

Dati di output

Il file output.txt contiene sulla prima riga il peso dell'albero e sulle successive N-1 righe le coppie u,v (separate da uno spazio) che rappresentano gli archi dell'albero.

Assunzioni

• 1 ≤ N ≤ 10000
• 2 ≤ M ≤ 1000000
• il grafo è semplice: non vi sono ne loops ne archi paralleli
• 1 ≤ w ≤ 2^{20} per il peso w di ciascun arco
• Il peso complessivo dell'MST è sicuramente ≤ 2^{36}

Esempi di input/output

7 9
1 2 7
2 3 21
1 3 14
1 4 30
4 3 10
3 5 1
5 6 6
5 7 9
6 7 4
    

42
1 2
1 3
3 4
3 5
5 6
6 7