7891

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
long x,z,y,i,n,m,a[1005][1005],f[1005],j,b[1005][1005];
long read()//快读
{
	long x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
void write(long x) {//快输
	if(x<0){
		putchar('-');
		write(-x);
		return;
	}
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
int main()
{
	n=read(),m=read();
	while(m--)
	{
		x=read();
		y=read();
		z=read();
		if(!b[x][y])a[x][y]=z;
		else a[x][y]=min(a[x][y],z);//有重复时找最大
		b[x][y]=1;
	}
	for(i=1;i<n;i++)f[i]=1e9;
	f[n]=0;//初始值
	for(i=n-1;i>=1;i--)
		for(j=i+1;j<=n;j++)
			if(a[i][j])f[i]=min(f[i],f[j]+a[i][j]);//如果连通，就找最短路径
	write(f[1]);
	return 0;
}```

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,z,f[50000],b[205][205];
int main()
{
  int i,j;
  cin>>n>>m;
  for(i=1;i<=200;++i)
  for(j=1;j<=200;++j)
  b[i][j]=1000000000000000;
  for(i=1;i<=m;++i)
  {
  	cin>>x>>y>>z;
  	b[x][y]=min(b[x][y],z);
  }
  for(i=n;i>=1;i--)
  {
  	for(j=1;j<=n;j++)
  	{
  	  if(f[i]>b[i][j]+f[j]&&b[i][j])//在两个点中插入一个点，使这两个点的距离通过新点变小
  	  {
  	  	f[i]=f[j]+b[i][j];
	  }
	}
  }
  cout<<f[1];
  return 0;
}