#include<vector>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<iostream>
#include<string.h>
#define LL long long
const int N = 5000;
using namespace std;
int n, m, v[N + 5];
int g[N + 5][N + 5];
LL dis1[N + 5], dis2[N + 5], dis[N * 40 + 5], k, p[N + 5];
vector< pair<int, LL > > edge[N + 5];
template<typename Tp>
void read(Tp &x) {
    x = 0;char c = getchar();int w = 1;
    for(; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            w = -1;
    for(; c <= '9' && c >= '0'; c = getchar())
        x = x * 10 + c - '0';
    x = x * w;          
}
void spfa1() {
    memset(dis1, 0x3f, sizeof(dis1));
    queue<int > q;
    while(!q.empty())
        q.pop();
    q.push(1);
    v[1] = 1;
    dis1[1] = 0;
    while(!q.empty()) {
        int w = q.front();v[w] = 0;
        q.pop();
        for(int i = 0; i < edge[w].size(); ++i)
            if (edge[w][i].second + dis1[w] < dis1[edge[w][i].first] && p[edge[w][i].first] >= k) {
                dis1[edge[w][i].first] = dis1[w] + edge[w][i].second;
                if (!v[edge[w][i].first]) {
                    v[edge[w][i].first] = 1;
                    q.push(edge[w][i].first);
                }
            }
        // q.pop();     
    }
}
void spfa2() {
    memset(dis2, 0x3f, sizeof(dis2));
    memset(v, 0,sizeof(v));
    queue<int > q;
    v[n] = 1;
    dis2[n] = 0;
    q.push(n);
    while(!q.empty()) {
        int w = q.front();v[w] = 0;
        for(int i = 0; i < edge[w].size(); ++i)
            if (edge[w][i].second + dis2[w] < dis2[edge[w][i].first] && p[edge[w][i].first] >= k) {
                dis2[edge[w][i].first] = dis2[w] + edge[w][i].second;
                if (!v[edge[w][i].first]) {
                    q.push(edge[w][i].first);
                    v[edge[w][i].first] = 1;
                }
            }
        q.pop();    
    }
}

LL max(LL x, LL y) {return x > y ? x: y;}
LL min(LL x, LL y) {return x < y ? x: y;}
int Maxx = 0x7fffffff, ans;
int main() {
   // freopen("tx.in", "r", stdin);
   // freopen("tx.out", "w", stdout);
    read(n);read(m);read(k);
    memset(g, 0x7f, sizeof(g));
    int inf = g[1][1];
    for(int i = 1; i <= m; ++i) {
        int x, y, c;
        read(x);read(y);read(c);
        if (x == y)
            continue;
        if (x > y) {
            int tp = x;
            x = y;
            y = tp; 
        }
        g[x][y] = min(g[x][y], c);  
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if (g[i][j] != inf) {
                edge[i].push_back(make_pair(j, g[i][j]));
                ++p[i];
                edge[j].push_back(make_pair(i, g[i][j]));
                ++p[j];
            }             
    p[1] = k + 1;
    p[n] = k + 1;   
    spfa1();
    // cout << dis1[n] << endl;
    spfa2();
    int tot = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < edge[i].size(); ++j) {
            int x = i, y = edge[i][j].first;
            if (p[x] >= k && p[y] >= k)
                dis[++tot] = dis1[x] + edge[i][j].second + dis2[y];
        }
    sort(dis + 1, dis + tot + 1);
    int i = 1; 
    for(; dis[i] == dis[1] && i <= tot; ++i);
    if (i > tot)
        cout << -1 << endl;
    else cout << dis[i] << endl;
    return 0;
}