renamePAL2

package pal;

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

/**
 *
 * @author Alisa
 */
public class Main {

    static public int N; //hotels counts = |vertexes|
    static public int M; //track counts = |edges|
    static public int[][] edges;
    static public int indexConnection = 0;
    static public boolean notConn = false;
    static public int[][] vertexes;

    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]);
        vertexes = new int[N][4]; //aktualni delka do vrcholu, delka posledni hrany vstoupivsi do vrcholu, delka predchozich hrany
        //////////////DADA KOMENT//////////////
        //takze
        //0-aktualni delka
        //1-posledni vstupujici hrana
        //2-posledni velikost kterou dovezla hrana s delkou ktera se rovna akrualni nejvetsi hrane ktera do uzlu vstoupila
        //3-nejvetsi vzdalenost kterou do uzlu dovezla hrana mensi nez nejvetsi ktera do uzlu vstupuje
        //////////////DADA KOMENT//////////////

        edges = new int[M][3]; //vrchol A, vrchol B, delka hrany AB
        int max = 0;
        for (int i = 0; i < M; i++) {
            in = br.readLine().split(" ");
            //x,y,z
            edges[i][0] = Integer.parseInt(in[0]); //x vertex
            edges[i][1] = Integer.parseInt(in[1]); //y vertex
            edges[i][2] = Integer.parseInt(in[2]); //distance between x and y
        }
        //sorted by distance
        edges = sortArrayByColumn(2);
        for (int i = 0; i < M; i++) {
            int bodA = edges[i][0];
            int bodB = edges[i][1];
            int delkaNoveHrany = edges[i][2];
            int maxDelkaA = vertexes[bodA][0];
            int maxDelkaB = vertexes[bodB][0];
            int posledniHranaA = vertexes[bodA][1];
            int posledniHranaB = vertexes[bodB][1];
            int delkaPosledniHranaA = vertexes[bodA][2];
            int delkaPosledniHranaB = vertexes[bodB][2];
            int delkaMinulaHranaA = vertexes[bodA][3];
            int delkaMinulaHranaB = vertexes[bodB][3];

            //predchozi hrana vrcholu A == soucasna hrana && predchozi hrana vrcholu B == soucasna hrana
            if (posledniHranaA == delkaNoveHrany && posledniHranaB == delkaNoveHrany) {   //delka do vrcholu A nebo B mensi jak nova hrana -> nahradime ji
                if (maxDelkaA < delkaNoveHrany) {
                    if (delkaPosledniHranaB < delkaMinulaHranaB + delkaNoveHrany) {
                        delkaPosledniHranaB = delkaMinulaHranaB + delkaNoveHrany;
                    }
//////////////////////DADA KOMENT ///////////////
//tady musis jeste pricist tu hodnotu z vertexes[cokoli][3]. To samy i o cca 15 radku niz
                    maxDelkaA = delkaNoveHrany + delkaMinulaHranaA;
//////////////////////DADA KOMENT ///////////////
                    if (delkaNoveHrany > max) {
                        max = delkaNoveHrany;
                    }
                }
                if (maxDelkaB < delkaNoveHrany + delkaMinulaHranaB) {
//////////////////////DADA KOMENT ///////////////
//prepis si na spravny promeny je to to samy co o par radku vysse jen s hodnotama pro druhej uzel
                    if (delkaPosledniHranaA < delkaMinulaHranaA + delkaNoveHrany) {
                        delkaPosledniHranaB= delkaMinulaHranaA + delkaNoveHrany;
                    }
//////////////////////DADA KOMENT ///////////////
                    maxDelkaB = delkaNoveHrany+posledniHranaB;
                    if (delkaNoveHrany > max) {
                        max = delkaNoveHrany;
                    }
                }
                continue;
            }
            //predchozi hrana vrcholu A a B != soucasna hrana
            if (posledniHranaA != delkaNoveHrany && posledniHranaB != delkaNoveHrany) {
                int help = maxDelkaA;
                //delka ve vrcholu A < nez B + nova cesta
                if (help < (maxDelkaB + delkaNoveHrany)) {
//////////////////////DADA KOMENT ///////////////
//tohle stejny jen pro druhy vrchol opet asi o 15 radku niz
                    if (delkaMinulaHranaA < delkaPosledniHranaA) {
                        delkaMinulaHranaA = delkaPosledniHranaA;
                    }
                    //nastavi velikost privedene cesty, aktualni cestou
                    delkaPosledniHranaA = posledniHranaA + delkaNoveHrany;
//////////////////////DADA KOMENT ///////////////
                    posledniHranaA = delkaNoveHrany;
                    maxDelkaA = maxDelkaB + delkaNoveHrany;
                    if (maxDelkaA > max) {
                        max = maxDelkaA;
                    }
                }
                //delka ve vrcholu B < nez A + nova cesta
                if (maxDelkaB < (help + delkaNoveHrany)) {
                    posledniHranaB = delkaNoveHrany;
                    maxDelkaB = help + delkaNoveHrany;
                    if (maxDelkaB > max) {
                        max = maxDelkaB;
                    }
                    delkaPosledniHranaA = posledniHranaA + delkaNoveHrany;
                }
                continue;
            }
            //predchozi hrana vrcholu A == soucasna hrana
            if (posledniHranaA == delkaNoveHrany) {
                int help = maxDelkaB;
                if (help < delkaNoveHrany + delkaMinulaHranaB) {
                    if (delkaPosledniHranaB < delkaMinulaHranaB + delkaNoveHrany) {
                        delkaPosledniHranaB = delkaMinulaHranaB + delkaNoveHrany;
                    }
                    delkaPosledniHranaB = posledniHranaB + delkaNoveHrany;
                    posledniHranaB = delkaNoveHrany;
                    maxDelkaB = delkaNoveHrany;
                    if (maxDelkaB > max) {
                        max = maxDelkaB;
                    }
                }
                if (help + delkaNoveHrany > maxDelkaA) {
//////////////////////DADA KOMENT ///////////////
//tady ti chybi zase ten jeden if, ted nevim presne kterej po prejmenovani se v tom ztracim
//////////////////////DADA KOMENT ///////////////
                    if (delkaPosledniHranaA < delkaMinulaHranaA + delkaNoveHrany) {
                        delkaPosledniHranaA = delkaMinulaHranaA + delkaNoveHrany;
                    }
                    delkaPosledniHranaA = posledniHranaA + delkaNoveHrany;
                    posledniHranaA = delkaNoveHrany;
                    maxDelkaA = help + delkaNoveHrany;
                    if (maxDelkaA > max) {
                        max = maxDelkaA;
                    }
                }
                continue;
            }
            //predchozi hrana vrcholu B == soucasna hrana
            if (posledniHranaB == delkaNoveHrany) {
                int help = maxDelkaA;
                if (help < delkaNoveHrany + delkaMinulaHranaA) {
                    if (delkaPosledniHranaA < delkaMinulaHranaA + delkaNoveHrany) {
                        delkaPosledniHranaA = delkaMinulaHranaA + delkaNoveHrany;
                    }
                    posledniHranaA = delkaNoveHrany;
                    maxDelkaA = delkaNoveHrany;
                    if (maxDelkaA > max) {
                        max = maxDelkaA;
                    }
                }
                if (help + delkaNoveHrany > maxDelkaB) {
//////////////////////DADA KOMENT ///////////////
//tady ti chybi zase ten jeden if, ted nevim presne kterej po prejmenovani se v tom ztracim
//////////////////////DADA KOMENT ///////////////\
                   if (delkaPosledniHranaB < delkaMinulaHranaB + delkaNoveHrany) {
                        delkaPosledniHranaB = delkaMinulaHranaB + delkaNoveHrany;
                    }
                    posledniHranaB = delkaNoveHrany;
                    maxDelkaB = help + delkaNoveHrany;
                    if (maxDelkaB > max) {
                        max = maxDelkaB;
                    }
                }
            }
        }
        System.out.println(max);
    }

    public static int[][] sortArrayByColumn(int column) {
        int[][] sortedArray = new int[M][3];
        int min = edges[0][column];
        int max = edges[0][column];
        //find min and max values for histogram from current column
        for (int i = 1; i < M; i++) {
            if (edges[i][column] < min) {
                min = edges[i][column];
            } else if (edges[i][column] > max) {
                max = edges[i][column];
            }
        }
        //histogram length from min to max
        int[] hist = new int[max - min + 1];
        for (int i = 0; i < M; i++) {
            hist[edges[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 = edges[i][column] - min;
            int index = hist[histIndex];
            sortedArray[index][column] = edges[i][column];
            sortedArray[index][1] = edges[i][1];
            sortedArray[index][0] = edges[i][0];
            hist[histIndex]--;
        }
        return sortedArray;
    }

}