diam graf

#include <iostream>
using namespace std;
///**********************
const int NMAX = 103;
int n, c[NMAX][NMAX], ans, m;

void read() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, cost;
        cin >> x >> y >> cost;
        c[x][y] = cost;
    }
}

void solve() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (c[i][k] && c[k][j] && i != j && (c[i][j] > c[i][k] + c[k][j] || !c[i][j])) {
                    c[i][j] = c[i][k] + c[k][j];
                    ans = max(ans, c[i][j]);
                }
}

int main() {
    read();
    solve();
    cout << ans << endl;
    return 0;
}