/*

  * Author:  Yzcstc

  * Created Time:  2014/11/5 19:25:47

  * File Name: revamp.cpp

  */

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<string>

 #include<map>

 #include<set>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<ctime>

 #define M0(x)  memset(x, 0, sizeof(int) * (n+10))

 #define MP make_pair

 #define x first

 #define y second

 using namespace std;

 typedef long long ll;

 typedef pair<ll, int> pii;

 const int maxn = ;

 struct edge{

     int v, w, next;

 } e[maxn * ];

 int last[maxn], tot;

 int n, k, m;

 void add(const int &u,const int &v, const int& w){

      e[tot] = (edge){v, w, last[u]}; last[u] = tot++;

 }

 void init(){

      int u, v, w;

      memset(last, -, sizeof(int) * (n * k + ));

      tot = ;

      for (int i = ; i < m; ++i){

           scanf("%d%d%d", &u, &v, &w);

           add(u, v, w); add(v, u, w);

           for (int i = ; i <= k; ++i){

                add(u + i * n, v + i * n, w);

                add(v + i * n, u + i * n, w);

                add(u + (i-) * n, v + i * n, );

                add(v + (i-) * n, u + i * n, );

           }

      }

 }

 ll dis[maxn];

 int vis[maxn];

 void dij(){

      priority_queue<pii, vector<pii>, greater<pii> > q;

      int nt = n * k + n;

      memset(vis, , sizeof(vis));

      for (int i = ; i <= nt; ++i) dis[i] = (1LL<<);

      pii tmp(, ); dis[] = ;

      q.push(tmp);

      int u, v;

      while (!q.empty()){

           u = q.top().y;

           q.pop();

           if (vis[u]) continue;

           vis[u] = ;

           for (int p = last[u]; ~p; p = e[p].next){

                v = e[p].v;

                if (dis[u] + e[p].w < dis[v]){

                     dis[v] = dis[u] + e[p].w;

                     tmp.x = dis[v], tmp.y = v;

                     q.push(tmp);

                }

           }

      }

 }

 void solve(){

      dij();

      ll ans = 1LL<<;

      for (int i = ; i <= k; ++i)

         ans = min(ans, dis[n+i*n]);

      cout << ans << endl;

 }

 int main(){

     freopen("a.in", "r", stdin);

     freopen("a.out", "w", stdout);

     clock_t start, finish;

     start = clock();

     while (scanf("%d%d%d", &n, &m, &k) != EOF){

          init();

          solve();

     }

     finish = clock();

     double t = (double)(finish - start) / CLOCKS_PER_SEC;

 //    printf("time = %.6f\n", t);

     return ;

 }