本题的决策内容是花费减半，所以层与层之间的权值不是0，而是这条边原权值的一半。

// 分层图最短路 分层建图 Dijkstra 算法 O(mk*log(nk))
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int N=55*51,M=1005*202;
int h[N],to[M],ne[M],w[M],idx;
void add(int a,int b,int c){
  to[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m,k;
int d[N];

void dijkstra(){
  memset(d,0x3f,sizeof d); d[1]=0;
  priority_queue<pii,vector<pii>,greater<pii>> q;
  q.emplace(0,1);
  while(q.size()){
    auto [dd,u]=q.top(); q.pop();
    if(dd!=d[u]) continue;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i];
      if(d[v]>d[u]+w[i]){
        d[v]=d[u]+w[i];
        q.emplace(d[v],v);
      }
    }
  }
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m>>k;
  for(int a,b,c;m--;){
    cin>>a>>b>>c;
    add(a,b,c),add(b,a,c); //0层双向边
    for(int i=1;i<=k;i++){
      add(a+i*n,b+i*n,c),add(b+i*n,a+i*n,c); //层内双向边
      add(a+(i-1)*n,b+i*n,c/2),add(b+(i-1)*n,a+i*n,c/2); //层间单向边
    }
  }
  dijkstra();
  int ans=2e9;
  for(int i=0;i<=k;i++) ans=min(ans,d[n+i*n]); //没走完k+1层，可能已经最小
  cout<<ans;
}