#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=1926817,MAXM=7186291,INF=2147483647;
struct Edge{
int to,Next,v;
}e[MAXM];
int n,m,s,front[MAXN],cnt,t,d1[MAXN],d2[MAXN];
inline void insert(int u,int v,int w){
++cnt;e[cnt].to=v;e[cnt].v=w;e[cnt].Next=front[u];front[u]=cnt;
}
void JuPaFA(int s,int *d){
int inq[MAXN];
queue<int>q;
memset(inq,0,sizeof(inq));
inq[s]=1;q.push(s);d[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();inq[u]=0;
for(int i=front[u];i>=0;i=e[i].Next){
int v=e[i].to,w=e[i].v;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!inq[v]){
q.push(v);
inq[v]=1;
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
s=1,t=n;
memset(front,-1,sizeof(front));
for(int i=1;i<=n;i++) d1[i]=d2[i]=INF;
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
insert(v,u,w);
}
JuPaFA(1,d1);
JuPaFA(t,d2);
int ans=INF;
for(int i=1;i<=n;i++){
for(int j=front[i];j>=0;j=e[j].Next){
v=e[j].to;
w=e[j].v;
int tmp=d1[i]+d2[v]+w;
if(tmp>d1[n]&&tmp<ans) ans=tmp;
}
}
printf("%d",ans);
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/151016.html
