code:

#include <bits/stdc++.h>
#define int long long
using namespace std;

class Matrix {
public:
    int n, m;
    vector<vector<unsigned int>> v;
    vector<unsigned int>& operator[](int x) {
        return v[x];
    }
    void resize(int r, int c) {
        n = r, m = c;
        v = vector<vector<unsigned int>>(n, vector<unsigned int>(m));
    }
};

Matrix base(int n) {
    Matrix ret;
    ret.resize(n, n);
    for (int i = 0; i < n; i++)
        ret[i][i] = 1;
    return ret;
}

Matrix operator*(Matrix a, Matrix b) {
    if (a.m != b.n)
        throw "a.m != b.n";
    Matrix c;
    c.resize(a.n, b.m);
    for (int i = 0; i < a.n; i++)
        for (int j = 0; j < b.m; j++)
            for (int k = 0; k < a.m; k++)
                c[i][j] += a[i][k] * b[k][j];
    return c;
}

int n, m, k, p = -1, ans;
Matrix f, g[65];

bool check(Matrix x) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += x[i][0] - 1;
        if (sum >= k) return 1;
    }
    return 0;
}

signed main() {
    cin >> n >> m >> k;
    f = base(3 * n + 1);
    f[0][0] = 0;
    g[0].resize(3 * n + 1, 3 * n + 1);
    g[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        g[0][i][0] = 1;
        g[0][i][i + n] = 1;
        g[0][i + n][i + 2 * n] = 1;
    }
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        g[0][u + (w - 1) * n][v]++;
    }
    for (int i = 1; i <= 64; i++) {
        g[i] = g[i - 1] * g[i - 1];
        if (check(g[i])) {
            p = i;
            break;
        }
    }
    if (p == -1) cout << -1 << endl;
    else {
        for (int i = p - 1; i >= 0; i--)
            if (!check(f * g[i])) {
                f = f * g[i];
                ans |= 1LL << i;
            }
        cout << ans << endl;
    }
    return 0;
}