28pts求助

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

const int N = 2e5+5;
int n,m;
ll dis[N<<1];
bool vis[N<<1];
vector<pii> e[N<<1],a[N];

void dij(){
    priority_queue<pii,vector<pii>,greater<pii> > q;
    for(int i=0;i<=m+1;i++) dis[i]=1e18;
    dis[0]=0,q.push({dis[0],0});
    while(!q.empty()){
        int x=q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(auto i : e[x]){
            int y=i.first,w=i.second;
            if(dis[y]>dis[x]+w){
                dis[y]=dis[x]+w;
                q.push({dis[y],y});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    // freopen("test.in","r",stdin);

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w; cin>>u>>v>>w;
        a[u].push_back({w,i}),a[v].push_back({w,i});
    }
    for(int i=2;i<n;i++){
        sort(a[i].begin(),a[i].end(),greater<pii>());
        for(int j=1;j<a[i].size();j++){
            e[a[i][j].second].push_back({a[i][j-1].second,max(a[i][j].first,a[i][j-1].first)});
            e[a[i][j-1].second].push_back({a[i][j].second,max(a[i][j].first,a[i][j-1].first)});
        }
    }
    for(auto i : a[1]) e[0].push_back({i.second,i.first});
    for(auto i : a[n]) e[i.second].push_back({m+1,i.first});
    dij();
    cout<<dis[m+1];
    return 0;
}