#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vl> matrix;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ff first
#define ss second
#define mp make_pair

const ll inf = 2e18;
const ll logi = 63;

static inline ll mul(ll a, ll b){
    if(!a || !b) return 0;
    __int128 x = __int128(a) * b;
    return x >= inf ? inf : ll(x);
}

static inline ll add(ll a, ll b){
    return min(a + b, inf);
}

matrix mnozenie(matrix& a, matrix& b){
    int n = a.size();
    matrix c(n, vl(n, 0));

    for(int i = 0; i < n; i++){
        for(int k = 0; k < n; k++){
            if(!a[i][k]) continue;
            for(int j = 0; j < n; j++){
                if(!b[k][j]) continue;
                c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
            }
        }
    }

    return c;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, m, k; cin >> n >> m >> k; k += n;

    vector<matrix> dp(logi);
    dp[0].assign(3 * n + 1, vl(3 * n + 1, 0));

    for(int i = 0; i < n; i++){
        dp[0][i + n][i] = 1;
        dp[0][i + 2 * n][i + n] = 1;
        dp[0][i][3 * n] = 1;
    }
    dp[0][3 * n][3 * n] = 1;

    for(int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c; a--; b--;
        int przes = n * (c - 1);
        dp[0][a][b + przes]++;
    }

    for(int i = 1; i < logi; i++){
        dp[i] = mnozenie(dp[i - 1], dp[i - 1]);
    }

    ll czy = 0;
    for(int i = 0; i < n; i++) czy = add(czy, dp[logi - 1][i][3 * n]);
    if(czy < k){
        cout << "-1\n"; return 0;
    }

    vl akt(3 * n + 1, 0); akt[3 * n] = 1;
    ll wyn = 0;
    for(int t = logi - 1; t >= 0; t--){
        vl kand(3 * n + 1, 0);
        for(int i = 0; i <= 3 * n; i++){
            if(!akt[i]) continue;
            for(int j = 0; j <= 3 * n; j++){
                kand[j] = add(kand[j], mul(akt[i], dp[t][j][i]));
            }
        }
        ll spr = 0;
        for(int i = 0; i < n; i++) spr = add(spr, kand[i]);
        if(spr < k){
            akt = kand;
            wyn += (1ll << t);
        }
    }


    cout << wyn << "\n";

    return 0;
}