#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int a, b, w;
}edges[M];

int n, m, k;
int dist[N], backup[N];

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    while(k --) {
        memcpy(backup, dist, sizeof dist);
        for(int i = 0; i < m; i ++) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            if(dist[b] > backup[a] + w)
                dist[b] = backup[a] + w;
        }
    }

    if(dist[n] > 0x3f >> 1) return -1;
    else return dist[n];
}

int main() {
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    int t = bellman_ford();

    if(t == -1) puts("-1");
    else cout << t << endl;

    return 0;
}