#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int dis[105];
int a[105][105];
bool op[105];
int pre[105];
int n,m;
int u,v,w;
int cnt;
void dij()
{
	for(int i=1;i<=n;++i)
	{
		op[i]=0;
		dis[i]=a[1][i];
	}
	dis[1]=0,pre[1]=0,op[1]=1;
	for(int i=1;i<=n;++i)
	{
		dis[101]=inf;
		int t=101;
		for(int j=1;j<=n;++j)
		{
			if(op[j]==0&&dis[t]>dis[j])
				t=j;
		}
		op[t]=1;
		for(int j=1;j<=n;++j)
		{
			if(dis[j]>dis[t]+a[t][j])
			{
				dis[j]=dis[t]+a[t][j];
				pre[j]=t;
			}
		}
	}	
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			a[i][j]=inf;
	for(int i=1;i<=m;++i)
	{
		cin>>u>>v>>w;
		a[u][v]=w;
		a[v][u]=w;
	}
	dij();		
	int minn=dis[n];
	int tmp=n;
	while(pre[tmp]!=0)
	{
		cnt++;
		tmp=pre[tmp];
	}
	int maxn=-1;
	tmp=n;
	for(int i=cnt;i>=1;i--)
	{
		a[pre[tmp]][tmp]*=2;
		dij();
		maxn=max(maxn,dis[n]);
		a[pre[tmp]][tmp]/=2;
		tmp=pre[tmp];
	}
	cout<<maxn-minn;
	return 0;
}

请教一下怎么修改