#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("traseu.in");
ofstream out("traseu.out");

const int NMax = 103, oo = 2e7;
int N, M, A[NMax][NMax], B[NMax][NMax];

void Citire (){
    in >> N >> M;
    int x, y, k;
    while (M--){
        in >> x >> y >> k;
        A[x][y] = k;
        B[x][y] = k;
    }
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (i != j && A[i][j] == 0)
                A[i][j] = oo;
}

void RoyFloyd (){
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
}

void Solve (){
    int S, Minim = 0;
    for (int i = 1; i <= N; ++i){
        S = 0;
        for (int j = 1; j <= N; ++j)
            S += (B[j][i] != 0) * (A[i][j] + B[j][i]);
        Minim = max (Minim , S);
    }
    out << Minim;
}

int main(){
    Citire();
    RoyFloyd();
    Solve();
    return 0;
}