```
#include <bits/stdc++.h>
using namespace std;
int n ,m ;
int head[5005];
int len;
struct Z{
int to ,next ,w ;
}e[200005];
void add(int u, int v, int w){
e[++len].next = head[u];
head[u] = len;
e[len].to = v;
e[len].w = w;
}
int dis1[5005], dis2[5005];
bool vis[5005];
queue<int> q;
void spfa(){
memset(dis1, 63, sizeof(dis1));
memset(dis2, 63, sizeof(dis2));
dis1[1] = 0;
vis[1] = 1;
q.push(1) ;
while(!q.empty() ){
int u = q.front();
q.pop();
vis[u] = 0;
for(int i = head[u]; i ; i = e[i].next){
int v = e[i].to;
int w = e[i].w;
bool flag = 0;
if(dis1[u] + w < dis1[v]){
dis2[v] = dis1[v];
dis1[v] = dis1[u] + w;
flag = 1;
}
else if(dis1[u] + w > dis1[v] && dis1[u] + w < dis2[v]){
dis2[v] = dis1[u] + w;
flag = 1;
}
if(dis2[u] + w<dis2[v]){
dis2[v] = dis2[u]+w;
flag = 1;
}
if(flag&&!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
}
int main(){
cin>>n >>m ;
for(int i = 1;i <= m;i ++){
int u,v,w;
cin >>u >>v >>w;
add(u ,v ,w );
add(v ,u ,w );
}
spfa();
cout<< dis2[n];
return 0;
}
```
by syl724 @ 2023-12-31 20:08:34