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