注意：如果是这么个写法，堆数组要开成n+m的。
为什么呢？设想一下从1到2有m条长度递减的路，这岂不是要入队m次……
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct Edge{
int too, nxt, val;
}edge[200005];
struct Node{
int idd, val;
}d[250005];//经luogu群大佬指点，这里是应该开成n+m的
int n, r, hea[5005], dis[5005], sdi[5005], cnt, k=0, uu, vv, ww;
void add_edge(int fro, int too, int val){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
edge[cnt].val = val;
hea[fro] = cnt;
}
bool cmp(Node x, Node y){
return x.val>y.val;
}
void dijkstra(){
memset(dis, 0x3f, sizeof(dis));
memset(sdi, 0x3f, sizeof(sdi));
dis[1] = 0;//源点最短是0，但次短是无穷。
Node ttt;
ttt.idd = 1;
ttt.val = 0;
d[++k] = ttt;
while(k){
Node j=d[1];
pop_heap(d+1, d+1+k, cmp);
k--;
if(j.val>sdi[j.idd]) continue;//保存的时候也许存的是次短或最短，但是倘若连保存的值比现在的次短还要大的话，就说明这个已经被搞过了，就不再处理它了，continue掉。
for(int i=hea[j.idd]; i; i=edge[i].nxt){
int t=edge[i].too;
int tmp=j.val+edge[i].val;
if(dis[t]>tmp){
swap(dis[t], tmp);//这里是swap而不是赋值。因为换下来的最短路还要留给次短路。
ttt.idd = t;
ttt.val = dis[t];
d[++k] = ttt;
push_heap(d+1, d+1+k, cmp);
}
if(dis[t]<tmp && sdi[t]>tmp){
sdi[t] = tmp;
ttt.idd = t;
ttt.val = sdi[t];
d[++k] = ttt;
push_heap(d+1, d+1+k, cmp);
}
}
}
}
int main(){
cin>>n>>r;
memset(hea, 0, sizeof(hea));
for(int i=1; i<=r; i++){
scanf("%d %d %d", &uu, &vv, &ww);
add_edge(uu, vv, ww);
add_edge(vv, uu, ww);
}
dijkstra();
cout<<sdi[n]<<endl;
return 0;
}