PAL2_3

package Main;

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

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;
    static public int[] length;

    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]);
        length = new int[N];
        hotels = new int[M][3];
        int max = 0;
        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);

        for (int i = 0; i < M; i++) {
            int helpOldLength = length[hotels[i][0]];
            if(helpOldLength < (length[hotels[i][1]] + hotels[i][2] ))
            {
                length[hotels[i][0]] = length[hotels[i][1]] + hotels[i][2];
                if(length[hotels[i][0]] > max) {max = length[hotels[i][0]];}
            }
            if(length[hotels[i][1]] < (helpOldLength + hotels[i][2] ))
            {
                length[hotels[i][1]] = helpOldLength + hotels[i][2];
                if(length[hotels[i][1]] > max) {max = length[hotels[i][1]];}
            }
        }
        System.out.println(max);
    }

      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];
            sortedArray[index][1] = hotels[i][1];
            sortedArray[index][0] = hotels[i][0];
            hist[histIndex]--;
        }
        return sortedArray;
    }
}