PAL2_1

package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author alisa
 */
public class PAL2 {

    static public int N; //hotels counts = |vertexes|
    static public int M; //track counts = |edges|
    static public int[][] hotels;
    static public int[][] hotelsHelp;
    static public int indexStart;
    static public int sum = 0;
    static public int indexHelp = 0;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        N = Integer.parseInt(in[0]);
        M = Integer.parseInt(in[1]);
        hotels = new int[M][3]; //x y z - uchovame puvodni informaci
        hotelsHelp = new int[M][2]; //x y - pouze prepisujeme vrcholy priznakem
        for (int i = 0; i < M; i++) {
            in = br.readLine().split(" ");
            //x,y,z
            hotels[i][0] = Integer.parseInt(in[0]); //x vertex
            hotels[i][1] = Integer.parseInt(in[1]); //y vertex
            hotels[i][2] = Integer.parseInt(in[2]); //distance between x and y
        }
        //sorted by distance
        hotels = sortArrayByColumn(2);
        int indexConn;
        int length = 0;
        for(int i = 0; i < M; i++)
        {   //hrana jeste nenavstivena a neoznackovana
            if(hotelsHelp[i][0] == 0 && hotelsHelp[i][1] == 0)
            {   //oznackuje vsechny shodne vrcholy
                setSameVertexes(i);
            }//hrana uz navstivena (oznackovana vzdalenosti)
            else
            {
                indexStart = i;
                indexConn = findConnection(i);
                setSameVertexes(i);
                length += hotels[indexConn][2];
            }
        }
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(hotels[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println(length);

    }
    /**
    *najde spojnici, pokud existuje, se kterou aktualni bod tvori vetsi soucet
    * @param index, od ktereho prohledavame vys
    * @return indexHelp = index spojnice, se kterou tvoji aktualni bod vetsi soucet
    */
    public static int findConnection(int index){
        int indexNext = 0;
        for(int i = index-1; index >= 0; i--)
        {   //shoduji-li se priznaky vrcholu
            if(hotelsHelp[indexStart][0] == hotelsHelp[i][0] || hotelsHelp[indexStart][1] == hotelsHelp[i][1])
            {   //first found - ulozime, aby sel vratit
                indexHelp = i;
                sum += (hotelsHelp[i][0] + hotels[indexStart][2]);
                //hledej dalsi spojnici
                indexNext = findConnection(i);
                //vetsi soucet nove spojnice, nova suma a hledame dal v dalsim foru
                if(hotelsHelp[indexNext][0] + hotels[indexStart][2] > sum ){
                   sum = hotelsHelp[indexNext][0] + hotels[indexStart][2];
                   indexHelp = indexNext;
                }
            }//neshoduji, hledej v podurovnii
            else{
                indexHelp = findConnection(i);
            }
        }
        //return 0 = zadny spoj, return cislo = nalezeny spoj
    return indexHelp;
    }
    /**
    *nastavit vsechny stejne vrcholy na stejny priznak
    * @param index, od ktereho nastavujeme niz
    */
    public static void setSameVertexes(int index) {
        for (int i = index + 1; i < M; i++) {
            //najdi vsechny dalsi stejne vrcholy a nastav jim priznak delkz
            int distance = hotels[0][2];
            if (hotels[i][0] == hotels[index][0]) {
                hotelsHelp[i][0] = distance;
            }
            if (hotels[i][1] == hotels[index][1]) {
                hotelsHelp[i][1] = distance;
            }
            //nastav priznak delky
            hotelsHelp[index][0] = distance;
            hotelsHelp[index][1] = distance;
        }
    }

    public static int[][] sortArrayByColumn(int column) {
        int[][] sortedArray = new int[M][3];
        int min = hotels[0][column];
        int max = hotels[0][column];
        //find min and max values for histogram from current column
        for (int i = 1; i < M; i++) {
            if (hotels[i][column] < min) {
                min = hotels[i][column];
            } else if (hotels[i][column] > max) {
                max = hotels[i][column];
            }
        }
        //histogram length from min to max
        int[] hist = new int[max - min + 1];
        for (int i = 0; i < M; i++) {
            hist[hotels[i][column] - min]++;
        }
//        for (int j = 0; j < hist.length; j++) {
//                System.out.print(hist[j] + " ");
//        }
        //pole vyskytu
        hist[0]--;
        for (int i = 1; i < hist.length; i++) {
            hist[i] = hist[i] + hist[i - 1];
        }
//        for (int j = 0; j < hist.length; j++) {
//                System.out.print(hist[j] + " ");
//        }
        //min to max
        for (int i = M - 1; i >= 0; i--) {
            int index = hist[hotels[i][column] - min];
            sortedArray[index][column] = hotels[i][column];
            sortedArray[index][1] = hotels[i][1];
            sortedArray[index][0] = hotels[i][0];
        }
        return sortedArray;
    }
}