#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m, z, a, b, c;
    cin >> n >> m >> z;

    vector<vector<pair<int, int>>> G(n);
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> c;  // a -> b, cena c
        G[a].push_back({b, c});
    }

    vector<int> dist(n, -1);

    // Floyd-Warshall
    // dist[i][j][k] = najkrajsa pot od i do j z uporabo prvih k vozlišč
    for (int i = 0; i < n; ++i) {
        dist[i][i] = 0;
    }
    for (int i = 0; i < n; ++i) {
        for (auto [c, w] : G[i]) {
            dist[i][c] = w;
        }
    }

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int better = dist[i][k] + dist[k][j];
                if (better > dist[i][j]) {
                    dist[i][j] = better;
                }
            }
        }
    }

    // natanko tedaj, ko je katerikoli izmed d[i][i] < 0, ima G negativen cikel

    return 0;
}