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

const int N=1005*1001,M=10005*4002;
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]>max(d[u],w[i])){
        d[v]=max(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,0),add(b+(i-1)*n,a+i*n,0); //层间单向边
    }
  }
  dijkstra();
  int ans=2e9;
  for(int i=0;i<=k;i++) ans=min(ans,d[n+i*n]); //没走完k+1层，可能已经最小
  if(ans>1000001) cout<<-1;
  else cout<<ans;
}

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

const int N=1005,M=10005*2;
int h[N],to[M],w[M],ne[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][1001]; //d[i][j]表示到达i用了j次免费的最小花费

void dijkstra(){
  memset(d,0x3f,sizeof d); d[1][0]=0;
  priority_queue<pii,vector<pii>,greater<pii>> q;
  q.emplace(0,1);
  while(q.size()){
    auto [dd,u]=q.top(); q.pop();
    int c=u/n; u=u%n; //哪层的哪个点
    if(dd!=d[u][c]) continue;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i];
      if(d[v][c]>max(d[u][c],w[i])){ //层内走路
        d[v][c]=max(d[u][c],w[i]);
        q.emplace(d[v][c],v+c*n);
      }
      if(c<k && d[v][c+1]>d[u][c]){ //层间走路
        d[v][c+1]=d[u][c];
        q.emplace(d[v][c+1],v+(c+1)*n);
      }
    }
  }
}
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);
  }
  dijkstra();
  int ans=2e9;
  for(int i=0;i<=k;i++) ans=min(ans,d[n][i]); //没走完k+1层，可能已经最小
  if(ans>1000001) cout<<-1;
  else cout<<ans;
}

二分+01BFS算法

边权分两类：>mid的边权，<=mid的边权 答案具有单调性，可以二分最大边权 将大于 mid 的边权看作 1，小于等于 mid 的边权看作 0 可以用 01BFS 求最短路

// 最短路 二分+01BFS算法 O((N+M)logL)
#include<bits/stdc++.h>
using namespace std;

const int N=1005,M=20005;
int h[N],to[M],w[M],ne[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],vis[N];

bool bfs(int mid){
  memset(vis,0,sizeof vis);
  memset(d,0x3f,sizeof d); d[1]=0;
  deque<int> q;
  q.push_back(1);
  while(q.size()){ //计算边权大于mid的边的条数 
    int u=q.front(); q.pop_front();
    if(vis[u]) continue;
    vis[u]=1;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i],x=(w[i]>mid);
      if(d[v]>d[u]+x){
        d[v]=d[u]+x;
        if(x==0) q.push_front(v);
        else q.push_back(v);
      }
    }
  }
  return d[n]<=k; //条数少，说明mid太大 
}
int main(){
  cin>>n>>m>>k;
  for(int a,b,c;m--;){
    cin>>a>>b>>c;
    add(a,b,c),add(b,a,c);
  }
  int l=0,r=1e6+1;
  while(l+1<r){  
    int mid=l+r>>1;
    if(bfs(mid)) r=mid;
    else l=mid;
  }
  if(r==1e6+1) cout<<-1;
  else cout<<r;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<pair<int, int>> G[N];
struct node {
    int x, y, z;
    bool operator<(const node& b) const { return x > b.x; }
};
int n, m, K, d[N][N]; bool v[N][N];//d[i][j]表示点1至点i在免费j条边情况下最大的边权 
void dijkstra() {
    memset(d, 0x3f, sizeof(d)); for (int i = 0; i <= K; i++) d[1][i] = 0;
    for (int i = 1; i <= n; i++) d[i][K + 1] = 0;
    memset(v, 0, sizeof(v));
    priority_queue<node> q; q.push({ 0, 1, 0 });
    while (!q.empty()) {
        int x = q.top().y, k = q.top().z; q.pop();
        if (v[x][k]) continue;
        v[x][k] = 1;
        for (auto i : G[x]) {
            int y = i.first, c = i.second;
            if (c > d[x][k]) {
                if (d[y][k] > c) {
                    d[y][k] = c;
                    q.push({ d[y][k], y, k });
                }
                if (d[y][k + 1] > d[x][k]) {
                    d[y][k + 1] = d[x][k];
                    q.push({ d[y][k + 1], y, k + 1 });
                }
            }
            else {
                if (d[y][k] > d[x][k]) {
                    d[y][k] = d[x][k];
                    q.push({ d[y][k], y, k });
                }
            }
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1, x, y, c; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &c);
        G[x].push_back({ y, c });
        G[y].push_back({ x, c });
    }
    dijkstra();
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= K; i++) ans = min(ans, d[n][i]);
    printf("%d", ans == 0x3f3f3f3f ? -1 : ans);
    return 0;
}