PAL2_2

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package Main;

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

/**
 *
 * @author martin
 */
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 indexConnection = 0;
    static public boolean notConn = false;


    /**
     * @param args the command line arguments
     * @throws java.io.IOException
     */
    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];
        hotelsHelp = new int[M][3];
        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
            hotelsHelp[i][2] = Integer.parseInt(in[2]) ;
        }
        //sorted by distance
        hotels = sortArrayByColumn(2);

        for (int i = M - 1; i >= 0; i--) {
            //nenavstiveno
            if (hotelsHelp[i][0] == 0 && hotelsHelp[i][1] == 0) {//nastavime priznak prislusnym vrcholum
                setSameVertexes(i);
            } else {//nastavime priznak prislusnym vrcholum
                addVisitedVertexes(i);
            }
            for (int k = M - 1; k >= 0; k--) {
                for (int l = 0; l < 3; l++) {
                    System.out.print(hotelsHelp[k][l] + " ");
                }
               System.out.println("") ;
            }
            System.out.println("xxx");
        }

    }

    public static void addVisitedVertexes(int currentVertex) {
        if((hotels[currentVertex][2] + hotelsHelp[currentVertex][0]) > (hotels[currentVertex][2] + hotelsHelp[currentVertex][1]))
        {
            System.out.println(hotels[currentVertex][2] + " " + hotelsHelp[currentVertex][0]);
            hotelsHelp[currentVertex][1] = (hotels[currentVertex][2] + hotelsHelp[currentVertex][0]);
            hotelsHelp[currentVertex][0] = (hotels[currentVertex][2] + hotelsHelp[currentVertex][0]);
            hotelsHelp[currentVertex][2] = (hotels[currentVertex][2] + hotelsHelp[currentVertex][0]);
        }
        if((hotels[currentVertex][2] + hotelsHelp[currentVertex][0]) < (hotels[currentVertex][2] + hotelsHelp[currentVertex][1]))
        {
            System.out.println(hotels[currentVertex][2] + " " + hotelsHelp[currentVertex][0]);
            hotelsHelp[currentVertex][1] = (hotels[currentVertex][2] + hotelsHelp[currentVertex][1]);
            hotelsHelp[currentVertex][0] = (hotels[currentVertex][2] + hotelsHelp[currentVertex][1]);
            hotelsHelp[currentVertex][2] = (hotels[currentVertex][2] + hotelsHelp[currentVertex][1]);
        }
        setSameVertexes(currentVertex);
    }

    public static void setSameVertexes(int currentVertex) {
        for (int i = currentVertex; i >= 0; i--) {
            //najdi vsechny dalsi stejne vrcholy a nastav jim nove delky
            int distance = hotelsHelp[currentVertex][2];
            if (hotels[i][0] == hotels[currentVertex][0]|| hotels[i][0] == hotels[currentVertex][1]) {
                hotelsHelp[i][0] = distance;
            }
            if (hotels[i][1] == hotels[currentVertex][1] || hotels[i][1] == hotels[currentVertex][0]) {
                hotelsHelp[i][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]++;
        }

        //pole vyskytu
        hist[0]--;
        for (int i = 1; i < hist.length; i++) {
            hist[i] = hist[i] + hist[i - 1];
        }

        //min to max
        for (int i = M - 1; i >= 0; i--) {
            int histIndex = hotels[i][column] - min;
            int index = hist[histIndex];
            sortedArray[index][column] = hotels[i][column];
            hotelsHelp[index][column] = hotels[i][column];
            sortedArray[index][1] = hotels[i][1];
            sortedArray[index][0] = hotels[i][0];
            hist[histIndex]--;
        }
        return sortedArray;
    }
}