#include <bits/stdc++.h>
// tiom4eg's precompiler options
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
// IO settings
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
// Quick types
#define ll long long
#define ull unsigned long long
#define pii pair <int, int>
#define vi vector <int>
#define mi vector <vector <int> >
// Segment tree
#define lp(x) (x + 1) >> 1
#define rp(x) (x - 1) >> 1
#define lk(x) x << 1
#define rk(x) (x << 1) + 1
// Quick functions
#define endl "\n"
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
#define fint(n) int n; cin >> n
#define fstr(s) string s; cin >> s
#define farr(a, n) int a[n]; for (int pog = 0; pog < n; ++pog) cin >> a[pog]
#define fprint(s) cout << s << endl
#define ffprint(s) fout << s << endl
#define bback(a) a[a.size() - 1]
#define arrprint(a) for (int lol = 0; lol < a.size(); ++lol) cout << a[lol] << ' ';
#define farrprint(a) for (int kek = 0; kek < a.size(); ++kek) fout << a[kek] << ' ';
// Quick fors
#define FOR1(s, n) for (int i = s; i < n; ++i)
#define FOR2(s, n) for (int j = s; j < n; ++j)
#define FOR3(s, n) for (int k = s; k < n; ++k)
#define RFOR(n, s) for (int l = n; l >= s; --l)
// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,fma")
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
using namespace std;

int main() {
    fastIO;
    int n, m, k; cin >> n >> m >> k;
    vector <pii> g[n];
    FOR1(0, m) {
        int a, b, t; cin >> a >> b >> t;
        a--, b--;
        g[a].pb({b, t});
        g[b].pb({a, t});
    }
    int d[n]; FOR1(0, n - 1) d[i] = 1e9;
    d[n - 1] = 0;
    for (int iter = 0; iter < n; ++iter) { // Iterations
        FOR1(0, n) { // Begins
            vector <pii> current;
            for (auto p : g[i]) current.pb({d[p.F] + p.S, p.S});
            sort(all(current));
            for (int l = 0; l < min(k, (int)current.size()); ++l) d[i] = min(d[i], current[l].F + current[l].S);
            if ((int)current.size() > k) d[i] = min(d[i], current[k].F);
        }
    }
    if (d[0] < 1e9) cout << d[0];
    else cout << -1;
}