#include <bits/stdc++.h>
#include <fstream>
#define int long long
#define TASK "minpath"
using namespace std;
const int MAXN = 1e2 + 7, oo = 3e18;
int N, M, K;
int G[MAXN][MAXN];
struct Matrix {
int M, N;
vector < vector < int > > v;
Matrix(int row = 0, int col = 0, int val = 0) {
M = row;
N = col;
v.assign(M, vector <int> (N, val));
}
Matrix operator * (const Matrix &A) {
int P = A.N;
Matrix res(M, P, +oo);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < P; ++j) {
for (int k = 0; k < N; ++k) {
res.v[i][j] = min(res.v[i][j], v[i][k] + A.v[k][j]);
}
}
}
return res;
}
Matrix operator ^ (int k) const {
Matrix res(N, N, +oo);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j)
res.v[i][j] = 0;
}
}
Matrix mul = *this;
while (k) {
if (k & 1) res = res * mul;
mul = mul * mul;
k >>= 1;
}
return res;
}
};
int ANS = +oo;
main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
#endif
cin >> N >> M >> K;
Matrix A(N, N, +oo);
for (int i = 1; i <= M; ++i) {
int u, v, c;
cin >> u >> v >> c;
A.v[u - 1][v - 1] = c;
}
Matrix res(1, N, 0);
res = res * (A ^ K);
for (int i = 0; i < N; ++i) {
ANS = min(ANS, res.v[0][i]);
}
if (ANS < (+oo) / 2)
cout << ANS << '\n';
else
cout << "IMPOSSIBLE" << '\n';
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxmc3RyZWFtPgoKI2RlZmluZSBpbnQgbG9uZyBsb25nCgojZGVmaW5lIFRBU0sgIm1pbnBhdGgiCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWE4gPSAxZTIgKyA3LCBvbyA9IDNlMTg7CgppbnQgTiwgTSwgSzsKaW50IEdbTUFYTl1bTUFYTl07CgpzdHJ1Y3QgTWF0cml4IHsKICAgIGludCBNLCBOOwogICAgdmVjdG9yIDwgdmVjdG9yIDwgaW50ID4gPiB2OwoKICAgIE1hdHJpeChpbnQgcm93ID0gMCwgaW50IGNvbCA9IDAsIGludCB2YWwgPSAwKSB7CiAgICAgICAgTSA9IHJvdzsKICAgICAgICBOID0gY29sOwogICAgICAgIHYuYXNzaWduKE0sIHZlY3RvciA8aW50PiAoTiwgdmFsKSk7CiAgICB9CgogICAgTWF0cml4IG9wZXJhdG9yICogKGNvbnN0IE1hdHJpeCAmQSkgewogICAgICAgIGludCBQID0gQS5OOwogICAgICAgIE1hdHJpeCByZXMoTSwgUCwgK29vKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBNOyArK2kpIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBQOyArK2opIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgTjsgKytrKSB7CiAgICAgICAgICAgICAgICAgICAgcmVzLnZbaV1bal0gPSBtaW4ocmVzLnZbaV1bal0sIHZbaV1ba10gKyBBLnZba11bal0pOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gcmVzOwogICAgfQoKICAgIE1hdHJpeCBvcGVyYXRvciBeIChpbnQgaykgY29uc3QgewogICAgICAgIE1hdHJpeCByZXMoTiwgTiwgK29vKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IE47ICsraSkgewogICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IE47ICsraikgewogICAgICAgICAgICAgICAgaWYgKGkgPT0gaikKICAgICAgICAgICAgICAgICAgICByZXMudltpXVtqXSA9IDA7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgTWF0cml4IG11bCA9ICp0aGlzOwoKICAgICAgICB3aGlsZSAoaykgewogICAgICAgICAgICBpZiAoayAmIDEpIHJlcyA9IHJlcyAqIG11bDsKICAgICAgICAgICAgbXVsID0gbXVsICogbXVsOwogICAgICAgICAgICBrID4+PSAxOwogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KfTsKCmludCBBTlMgPSArb287CgptYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBjb3V0LnRpZShOVUxMKTsKCiNpZm5kZWYgT05MSU5FX0pVREdFCglmcmVvcGVuKFRBU0siLmlucCIsICJyIiwgc3RkaW4pOwoJZnJlb3BlbihUQVNLIi5vdXQiLCAidyIsIHN0ZG91dCk7CiNlbmRpZgoKICAgIGNpbiA+PiBOID4+IE0gPj4gSzsKICAgIE1hdHJpeCBBKE4sIE4sICtvbyk7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBNOyArK2kpIHsKICAgICAgICBpbnQgdSwgdiwgYzsKICAgICAgICBjaW4gPj4gdSA+PiB2ID4+IGM7CiAgICAgICAgQS52W3UgLSAxXVt2IC0gMV0gPSBjOwogICAgfQoKICAgIE1hdHJpeCByZXMoMSwgTiwgMCk7CgogICAgcmVzID0gcmVzICogKEEgXiBLKTsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47ICsraSkgewogICAgICAgIEFOUyA9IG1pbihBTlMsIHJlcy52WzBdW2ldKTsKICAgIH0KCiAgICBpZiAoQU5TIDwgKCtvbykgLyAyKQogICAgICAgIGNvdXQgPDwgQU5TIDw8ICdcbic7CiAgICBlbHNlCiAgICAgICAgY291dCA8PCAiSU1QT1NTSUJMRSIgPDwgJ1xuJzsKCn0K