玄学解法，不知道对不对，

#include <bits/stdc++.h>
using namespace std;
int pre[5010],pren[5010],vis[5010],ans,n,m,cnt,tot,head[5010],sxdhy[5010];
long long dis[5010],maxx;
struct edge{
	int next,to;long long val;
}a[501000];
void add(int x,int y,int z){
	a[++cnt].next=head[x];
	a[cnt].to=y;
	a[cnt].val=z;
	head[x]=cnt;
}
queue<int >q;
void spfa(int x){
	memset(dis,127,sizeof(dis));
	dis[x]=0;
	q.push(x);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=a[i].next){
			int v=a[i].to;
			if(dis[v]>dis[u]+a[i].val){
				pre[v]=i;
				pren[v]=u;
				dis[v]=a[i].val+dis[u];
				if(vis[v]==0){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	memset(pren,-1,sizeof(pren));
	spfa(1);
	ans=dis[n];
	int dhy=n;
	while(1){
		if(dhy==1)break;
		sxdhy[++tot]=pre[dhy];
		dhy=pren[dhy];
	}
	long long ans2=1e7;
	for(int i=1;i<=tot;i++){
		int num=sxdhy[i];
		int also;if(num%2==0)also=num-1;else also=num+1;
		a[num].val*=3;
		a[also].val*=3;
		spfa(1);
		if(dis[n]>ans){
			ans2=min(ans2,dis[n]);
		}
		a[num].val/=3;
		a[also].val/=3;
	}
	cout<<ans2;
}