mst (mst)

Tempo limite 1 sec.

Descrizione del problema

Si calcoli un minimo albero ricoprente (MST) di un grafo pesato non orientato avente N nodi e M archi. Un MST (Minimum Spanning Tree) \'e un sottoinsieme T degli archi del grafo, a somma dei pesi minima, tale che per ogni due nodi del grafo esista un cammino in T che li connetta.

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

Esempi di input/output

File input.txtFile output.txt
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