FREETICKET Solutio

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.math.*;

public class FREETICKET{

    public static final int INF = Integer.MAX_VALUE;

    public static void main(String args[]) throws IOException {
        Scanner in = new Scanner(System.in);

        int c = in.nextInt();
        int f = in.nextInt();

        int[][] flights = new int[c][c];

        for (int i = 0; i < c; i++) {
            for (int j = 0; j < c; j++) {
                flights[i][j] = -1;
            }
        }

        for (int i = 0 ; i < f; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            int w = in.nextInt();
            flights[a][b] = w;
            flights[b][a] = w;
        }

        int max_cost = -10;

        for (int i =0; i < c; i++) {
            int[] dist = new int[c];
            boolean[] visited = new boolean[c];

            for (int j = 0; j < c; j++) {
                dist[j] = flights[i][j];
                visited[j] = false;
            }

            visited[i] = true;

            while (true) {
                int min_flight = -1;
                int min_dist = INF;

                for (int j = 0; j < c ; j++) {
                    if (dist[j] != -1 && !visited[j] && dist[j] < min_dist) {
                        min_dist = dist[j];
                        min_flight = j;
                    }
                }

                if (min_flight == -1) {
                    break;
                }

                visited[min_flight] =  true;

                if (min_dist> max_cost) {
                    max_cost = min_dist;
                }

                for (int j = 0; j < c; j++) {
                    if (flights[min_flight][j] != -1) {
                        if (dist[j] == -1 || dist[j] > min_dist + flights[min_flight][j]) {
                            dist[j] = min_dist + flights[min_dist][j];
                        }
                    }
                }


            }



        }

        System.out.println(max_cost);
    }
}