import java.util.List;
import java.util.Scanner;
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;


public class Main {
	static int SW=0;
	static int POM;
	static int WSK=0;
        static class Krawedz
        {
                int waga;
                int poczatek, koniec;
                public Krawedz(int w, int b, int e)
                {
                        waga = w;
                        poczatek = b;
                        koniec = e;
                }
        }

        public static void main(String[] args) throws IOException {

            Scanner odczyt = new Scanner(new File("In0303.txt"));
            PrintWriter zapis = new PrintWriter("Out0303.txt");
            String line = odczyt.nextLine();
            String[] first = line.split(" ");
            int n = Integer.parseInt(first[0]);
            int m = Integer.parseInt(first[1]);
            int[] Kruskal = new int[n+1];
            for(int i=1;i<=n;i++)
            {
            	Kruskal[i]=i;
            }

            int[] X = new int[n+1];

                List<Krawedz> E = new ArrayList<Krawedz>();
            for(int i=0; i<n; i++)
            {
                line = odczyt.nextLine();
                String[] number = line.split(" ");
                for(int k=0; k<number.length; k++)
                        number[k] = number[k].replace(",", "");
                for(int k=0; k<number.length; k+=2)
                {
                        number[k] = number[k].replace(",", "");
                        int w = Integer.parseInt(number[k+1]);
                        int e = Integer.parseInt(number[k]);
                        E.add(new Krawedz(w, i+1, e));
                }
            }
            //sprawdzenia max wagi
            int mw=0;
            for(Krawedz k: E)
            {
            	if(mw<k.waga)mw=k.waga;
            }

    List<Krawedz> Posortowana = new ArrayList<Krawedz>();
    for(int i=1;i<mw;i++)
    {
    for(Krawedz k:E)
    {
    	if(k.waga==i){Krawedz n1 = new Krawedz(k.waga,k.poczatek,k.koniec); Posortowana.add(n1);}
    }
    }
    for(Krawedz k: Posortowana)
    {
    	if(Kruskal[k.poczatek]!=Kruskal[k.koniec])
    	{
    		SW+=k.waga;
    		zapis.print(k.poczatek+" "+k.koniec+" "+"["+k.waga+"]"+"  ");
    		int x,y;
    		x=Kruskal[k.poczatek];y=Kruskal[k.koniec];
    		if(Kruskal[k.poczatek]>Kruskal[k.koniec]){ for(int i=1;i<=n;i++){if(Kruskal[i]==x || Kruskal[i]==y)Kruskal[i]=x; } }
    		else { for(int i=1;i<=n;i++){if(Kruskal[i]==x || Kruskal[i]==y)Kruskal[i]=y; } }
    	}
    	for(int i=1;i<=n;i++)
    	{
    		POM=Kruskal[i];
    		if(Kruskal[i]==POM) WSK++;
    	}
    	if(WSK==( n-1) )break;
    	WSK=0;
    }
//    for(Krawedz k: Posortowana)
//    {
//    	System.out.println(k.poczatek+" "+k.koniec+" "+k.waga);
//    }
    for(int i=1;i<=n;i++)
    {
    	System.out.println(Kruskal[i]);
    }
    zapis.println("SUMA WAG: "+SW);
    zapis.close();
}
}