#include <cstdio>
#include <algorithm>
typedef long long ll;
const int N = 110;
const ll inf = 1e15;
struct Matrix
{
    ll a[N][N];
    int n, m;
    Matrix(int n = 0, int m = 0) : n(n), m(m) {}
    void init()
    {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                a[i][j] = (i == j) ? 0 : inf;
    }
    Matrix operator * (const Matrix &A) const
    {
        Matrix ret(n, A.m);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= A.m; ++j) {
                ll o = inf;
                for (int k = 1; k <= m; ++k)
                    o = std::min(o, a[i][k] + A.a[k][j]);
                ret.a[i][j] = o;
            }
        return ret;
    }
};
Matrix ksm(Matrix A, int b) {
    Matrix ret(A.n, A.n);
    ret.init();
    while (b) {
        if (b & 1)
            ret = ret * A;
        A = A * A;
        b >>= 1;
    }
    return ret;
}
int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    Matrix E(n, n), K(n, n);
    E.init();
    K.init();
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        E.a[v][u] = w;
        K.a[v][u] = -w;
    }
    Matrix G = ksm(E, n - 1);
    G = G * ksm(K * G, k);
    printf("%lld\n", G.a[n][1]);
    return 0;
}