给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出从1号点走到n号点并且必须途经k号点(k≠1≠n)的最短距离，如果不存在这样的路径，则输出-1。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int N=150000+10,M=N;

int h[N],e[M],ne[M],w[M],idx;

int n,m,dist[N][2],k;
bool st[N][2];
void add(int a,int b,int v)
{
    e[idx]=b,w[idx]=v,ne[idx]=h[a],h[a]=idx++;
}
int dij()
{
    memset(dist,0x3f,sizeof dist);
    dist[1][0]=0;

    priority_queue<PIII,vector<PIII>,greater<PIII>> heap;
    heap.push({0,{1,0}});
    while(heap.size())
    {
        PIII t=heap.top();
        heap.pop();
        int ver=t.second.first,state=t.second.second;
        if(st[ver][state]) continue;
        st[ver][state]=true;

        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i],ns=0;
            if(state||j==k) ns=1;
            if(dist[j][ns]>dist[ver][state]+w[i])
            {
                dist[j][ns]=dist[ver][state]+w[i];
                heap.push({dist[j][ns],{j,ns}});
            }
        }
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>k;
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dij();
    if(dist[n][1]>=1e9) cout<<-1;
    else cout<<dist[n][1]<<endl;
    return 0;
}