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