ABC 208

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector dist(N, vll(N, INF));
    rep(i, M) {
        ll u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        dist[u][v] = c;
    }
    rep(i, N) dist[i][i] = 0;

    ll ans = 0;
    rep(k, N) {
        rep(i, N) {
            rep(j, N) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
                if (dist[i][j] != INF) {
                    ans += dist[i][j];
                }
            }
        }
    }
    cout << ans << endl;
}