PAL_22-10_1

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][3]; //aktualni delka do vrcholu, velikost posledni hrany vstoupivsi do vrcholu, delka vcetne predposledni hrany
        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]) - 1; //x vertex
            edges[i][1] = Integer.parseInt(in[1]) - 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++) {
            //predchozi hrana vrcholu A == soucasna hrana && predchozi hrana vrcholu B == soucasna hrana
            if (vertexes[edges[i][0]][1] == edges[i][2] && vertexes[edges[i][1]][1] == edges[i][2]) {   //delka do vrcholu A nebo B mensi jak nova hrana -> nahradime ji
//                if (vertexes[edges[i][0]][0] < edges[i][2]) {
//                    vertexes[edges[i][0]][2] = vertexes[edges[i][0]][0];
//                    vertexes[edges[i][0]][0] = edges[i][2];
//                    if (edges[i][2] > max) {
//                        max = edges[i][2];
//                    }
//                }
//                if (vertexes[edges[i][1]][0] < edges[i][2]) {
//                    vertexes[edges[i][1]][2] = vertexes[edges[i][1]][0];
//                    vertexes[edges[i][1]][0] = edges[i][2];
//                    if (edges[i][2] > max) {
//                        max = edges[i][2];
//                    }
//                }

                //minula delka hrany + nova hrana > soucasna
                if (vertexes[edges[i][0]][2] + edges[i][2] > vertexes[edges[i][1]][0]) {
                    //minula delka hrany nastavena
   //                 System.out.println("double == x1prev +b > x2act");
  //                  System.out.println(edges[i][0] + 1 + " " + edges[i][1] + 1);
 //                   System.out.println(vertexes[edges[i][0]][2] + " " + edges[i][2] + " > " + vertexes[edges[i][1]][0]);
                    vertexes[edges[i][1]][2] = vertexes[edges[i][0]][0];
                    //nova delka nastavena
                    vertexes[edges[i][1]][0] = vertexes[edges[i][0]][2] + edges[i][2];
 //                   System.out.println("nova delka " + vertexes[edges[i][1]][0] + " nova minula hrana " + vertexes[edges[i][1]][2]);
                    if (vertexes[edges[i][0]][2] + edges[i][2] > max) {
                        max = vertexes[edges[i][0]][2] + edges[i][2];
                    }
                }

                if (vertexes[edges[i][1]][2] + edges[i][2] > vertexes[edges[i][0]][0]) {
                    //minula delka hrany nastavena
   //                 System.out.println("double == x2prev +b > x1act");
   //                 System.out.println(edges[i][0] + 1 + " " + (edges[i][1] + 1));
    //                System.out.println(vertexes[edges[i][1]][2] + " " + edges[i][2] + " > " + vertexes[edges[i][0]][0]);
                    vertexes[edges[i][0]][2] = vertexes[edges[i][1]][0];
                    //nova delka nastavena
                    vertexes[edges[i][0]][0] = vertexes[edges[i][1]][2] + edges[i][2];
 //                   System.out.println("nova delka " + vertexes[edges[i][0]][0] + " nova minula hrana " + vertexes[edges[i][0]][2]);
                    if (vertexes[edges[i][1]][2] + edges[i][2] > max) {
                        max = vertexes[edges[i][1]][2] + edges[i][2];
                    }
                }
            }

            //predchozi hrana vrcholu A && B != soucasna hrana
            if (vertexes[edges[i][0]][1] != edges[i][2] && vertexes[edges[i][1]][1] != edges[i][2]) {
                int help = vertexes[edges[i][0]][0];
                //delka ve vrcholu A < nez B + nova cesta
                if (help < (vertexes[edges[i][1]][0] + edges[i][2])) {
   //                 System.out.println("zadna se nerovna x1act < x2act + b");
  //                  System.out.println(edges[i][0] + 1 + " " + (edges[i][1] + 1));
  //                  System.out.println(vertexes[edges[i][1]][0] + "+" + edges[i][2] + " > " + help);
                    vertexes[edges[i][0]][1] = edges[i][2];
                    vertexes[edges[i][0]][2] = help;
                    vertexes[edges[i][0]][0] = vertexes[edges[i][1]][0] + edges[i][2];
 //                   System.out.println("nova delka " + vertexes[edges[i][0]][0] + " nova minula hrana " + vertexes[edges[i][0]][2]);
                    if (vertexes[edges[i][0]][0] > max) {
                        max = vertexes[edges[i][0]][0];
                    }
                }
                //delka ve vrcholu B < nez A + nova cesta
                if (vertexes[edges[i][1]][0] < (help + edges[i][2])) {
 //                   System.out.println("zadna se nerovna x2act < x1act + b");
 //                   System.out.println(edges[i][0] + 1 + " " + (edges[i][1] + 1));
  //                  System.out.println(help + "+" + edges[i][2] + " > " + vertexes[edges[i][1]][0]);
                    vertexes[edges[i][1]][1] = edges[i][2];
                    vertexes[edges[i][1]][2] = vertexes[edges[i][1]][0];
                    vertexes[edges[i][1]][0] = help + edges[i][2];
 //                   System.out.println("nova delka " + vertexes[edges[i][1]][0] + " nova minula hrana " + vertexes[edges[i][1]][2]);
                    if (vertexes[edges[i][1]][0] > max) {
                        max = vertexes[edges[i][1]][0];
                    }

                }
                continue;
            }
            //predchozi hrana vrcholu A == soucasna hrana
            if (vertexes[edges[i][0]][1] == edges[i][2]) {
                int help = vertexes[edges[i][1]][0];

                if (help + edges[i][2] > vertexes[edges[i][0]][0] && edges[i][2] != vertexes[edges[i][0]][1]) {
 //                   System.out.println("x1 == b, x1<x2+nova hrana");
                    vertexes[edges[i][0]][1] = edges[i][2];
                    vertexes[edges[i][0]][2] = vertexes[edges[i][0]][0];
                    vertexes[edges[i][0]][0] = help + edges[i][2];
 //                   System.out.println("act delka " + vertexes[edges[i][0]][0] + " min hrana " + vertexes[edges[i][0]][2] + "minula delka" + vertexes[edges[i][0]][1]);
                    if (vertexes[edges[i][0]][0] > max) {
                        max = vertexes[edges[i][0]][0];
                    }
                    continue;
                }
                if (help < edges[i][2]) {
  //                  System.out.println("x1 == b, x2<b");
                    vertexes[edges[i][1]][1] = edges[i][2];
                    vertexes[edges[i][1]][2] = vertexes[edges[i][1]][0];
                    vertexes[edges[i][1]][0] = edges[i][2];
  //                  System.out.println("act delka " + vertexes[edges[i][1]][0] + " min hrana " + vertexes[edges[i][1]][2] + "minula delka" + vertexes[edges[i][1]][1]);
                    if (vertexes[edges[i][1]][0] > max) {
                        max = vertexes[edges[i][1]][0];
                    }
                    continue;
                }

            }
            //predchozi hrana vrcholu B == soucasna hrana
            if (vertexes[edges[i][1]][1] == edges[i][2]) {
                int help = vertexes[edges[i][0]][0];

                if (help + edges[i][2] > vertexes[edges[i][1]][0] && edges[i][2] != vertexes[edges[i][1]][1])  {
  //                  System.out.println("x2 == b, x2<b+nova hrana");
                    vertexes[edges[i][1]][1] = edges[i][2];
                    vertexes[edges[i][1]][2] = vertexes[edges[i][0]][0];
                    vertexes[edges[i][1]][0] = help + edges[i][2];
   //                 System.out.println("act delka " + vertexes[edges[i][1]][0] + " min hrana " + vertexes[edges[i][1]][2] + "minula delka" + vertexes[edges[i][1]][1]);
                    if (vertexes[edges[i][1]][0] > max) {
                        max = vertexes[edges[i][1]][0];
                    }
                    continue;
                }
                if (help < edges[i][2]) {
  //                  System.out.println("x2 == b, x1<b");
                    vertexes[edges[i][0]][1] = edges[i][2];
                    vertexes[edges[i][0]][2] = vertexes[edges[i][1]][0];
                    vertexes[edges[i][0]][0] = edges[i][2];
 //                   System.out.println("act delka " + vertexes[edges[i][0]][0] + " min hrana " + vertexes[edges[i][0]][2] + "minula delka" + vertexes[edges[i][0]][1]);
                    if (vertexes[edges[i][0]][0] > max) {
                        max = vertexes[edges[i][0]][0];
                    }
                }

            }
        }
        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;
    }

}