KPATH

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

template<typename A, typename B> A power(A a, B b) {if (b == 1) return a; A t = power(a, b / 2); return (b & 1 ? t * t * a : t * t);}

const int N = 1e2 + 5;

typedef vector<int64_t> v64;

int64_t n, m, k;
vector<v64> adj;
int64_t ans = 0;
vector<v64> multi;

vector<v64> operator *(vector<v64> a, vector<v64> b) {
    int n = a.size();
    int p = a[0].size();
    int m = b[0].size();

    vector<v64> d(n + 5, v64 (m + 5, -1));

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            for(int t = 0; t < p; ++t)
                if (a[i][t] != -1 && b[t][j] != -1) {
                    d[i][j] = max(d[i][j], a[i][t] + b[t][j]);
                }

    return d;
}


int main() {
    freopen("in.txt", "r", stdin);
    //freopen("KPATH.inp", "r", stdin);
    //freopen("KPATH.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> k;

    adj.resize(n + 1, v64(n + 1, -1));

    for(int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        adj[u][v] = c;
    }

    multi = power(adj, k);

    int64_t ans = -1;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
            ans = max(ans, multi[i][j]);

    cout << ans << '\n';

    return 0;
}