#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f;
int n, m, T;
// 邻接表
int idx, e[N], ne[N], h[N], w[N];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int backup[N]; // 拷贝一下d数组,避免出现串联
int d[N];      // 最短距离

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

    while (T--) {
        memcpy(backup, d, sizeof d);            // 每次更新前memcpy避免出现串联
        for (int u = 1; u <= n; u++)            // 执行n次松驰操作
            for (int i = h[u]; ~i; i = ne[i]) { // 枚举每个出边
                int v = e[i];
                d[v] = min(d[v], backup[u] + w[i]);
            }
    }
    if (d[n] > INF / 2) return INF; // 因为有负权边所以可能出现d[n]比0x3f3f3f3f稍微小一些
    return d[n];
}
int main() {
    cin >> n >> m >> T;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = bellman_ford();
    if (t == INF)
        puts("impossible");
    else
        cout << t << endl;
    return 0;
}