#include<iostream>
#include<cstring>
#include<queue>
#define int long long
#define mkp make_pair
#define sec second 
#define fir first 
using namespace std;
const int maxn=2e5+10;
//题目是分层图
//我们把免费操作转化成零边，如果进行免费操作，就进入下一层
//就是说,可以建好几层图,第0层就是一条边也不去掉,第1曾去掉最大的那条边,第2曾去掉前2大的边.....
int n,p,k;
int head[maxn],nex[maxn],ver[maxn],edge[maxn],tot;
int d[1001][1001];//或者是d[i][j]是到i点,去掉j条边后的最大值中的最小值(看到这里应该想到似乎可以二分)
bool ju[1001][1001];
priority_queue<pair<int, pair<int,int>>>q;
inline void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    nex[tot]=head[x];
    head[x]=tot;
}
void dijkstra()
{
    memset(d,0x7f7f,sizeof(d));
    d[1][0]=0;
    q.push(make_pair(0,mkp(1,0)));
    while(q.size())
    {
        int x=q.top().sec.fir,l=q.top().sec.sec;
        q.pop();
        if(ju[x][l])continue;//从1到x
        ju[x][l]=1;
        for(int i=head[x];i;i=nex[i])
        {
            int y=ver[i],z=edge[i];//x可以直接连到y
            if(d[y][l]>max(d[x][l],z))//同一层 从x->y还有个边x,如果到y时去掉l条边后的值不如先去掉l条边到x再到y小
            //(就是说走x这条路可以获得更小的值),
            //为什么max(d[x],z)呢,因为此路线中的最大的中的第l+1个是d[x]或者d[x]<z的话
            //就要把z插在d[x]值前面,就是说此路线中的最大的中的第l+1个变成了z
            {
                d[y][l]=max(d[x][l],z);
                q.push(mkp(-d[y][l],mkp(y,l)));
            }
            if(l<k&&d[y][l+1]>d[x][l])//这里是说把x,y之间的边free掉,那么进入下一层图,至于为什么是大于,还是因为x线路存在更优解
            {
                d[y][l+1]=d[x][l];
                q.push(mkp(-d[y][l+1],mkp(y,l+1)));
            }
        }
    }
}
signed main()
{
    cin>>n>>p>>k;
    for(int i=1;i<=p;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    dijkstra();
    int ans=0x7f7f7f7f;
    for(int i=0;i<=k;i++)//防止没有走k层就到n了
    ans=min(ans,d[n][i]);
    if(ans==0x7f7f7f7f)cout<<-1;
    else cout<<ans<<endl;
    return 0;
}

 #include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define int long long
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
using namespace std;
const int maxn=6e6+10;
int n,m,stx,sty,enx,eny;
int ver[maxn],val[maxn],head[maxn],nex[maxn],tot,d[maxn];
struct station
{
    int id;
    int x,y;
}a[maxn];
bool cmp1(station i,station j)
{
    if(i.x==j.x)return i.y<j.y;
    return i.x<j.x;
}
bool cmp2(station _,station __)
{
    if(_.y==__.y)return _.x<__.x;
    return _.y<__.y;
}
priority_queue<pii>q;
bool ju[maxn];
void dijkstra(int s)
{
    memset(d,0x7f7f7f,sizeof(d));
    d[s]=0;
    q.push(mkp(0,s));
    while(!q.empty())
    {
        int x=q.top().sec;
        q.pop();
        if(ju[x])continue;
        ju[x]=1;
        for(int i=head[x];i;i=nex[i])
        {
            int y=ver[i],z=val[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(mkp(-d[y],y));
            }
        }
    }
    
}
inline void add(int x,int y,int z)
{
    ver[++tot]=y;
    val[tot]=z;
    nex[tot]=head[x];
    head[x]=tot;
}
inline void addd(int x,int y,int z)
{
    add(x,y,z);
    add(y,x,z);
}
signed main()
{
    cin>>n>>m;
    if(m==0)//特判一下
    {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=m+2;i++)
    {
        cin>>a[i].x>>a[i].y;
        a[i].id=i;
    }
    sort(a+1,a+m+3,cmp1);
    for(int i=1;i<=m+1;i++)
    {
        if(a[i].x==a[i+1].x)
        {
            addd(a[i].id,a[i+1].id,(a[i+1].y-a[i].y)*2);
        }
    }
    sort(a+1,a+m+3,cmp2);
    for(int i=1;i<=m+1;i++)
    {
        if(a[i].y==a[i+1].y)
        {
            addd(a[i].id+m+2,a[i+1].id+m+2,(a[i+1].x-a[i].x)*2);
        }
    }
    for(int i=1;i<=m;i++)addd(i,i+m+2,1);//两层图建边
    addd(m+1,m+1+m+2,0);
    addd(m+2,m+2+m+2,0);
    dijkstra(m+1);
    if(d[m+2]==0x7f7f7f)cout<<-1;
    else cout<<d[m+2];
    return 0;
}