rt

#include <bits/stdc++.h>
using namespace std;
const long long inf=1e18;
const int N=1e3+10;
long long G[N][N];
long long f[N][N];
bool vis[N][N];
int pre[N];
long long dis[N];
bool v[N];
long long fulldis;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
  		for(int j=1;j<=n;j++)
		{
	   		if(i==j) G[i][j]=0;
	  		else G[i][j]=inf;
  		}
 	}
 	for(int i=1;i<=m;i++)
	{
 		int u,v,w;
		cin>>u>>v>>w;
  		G[u][v]=G[v][u]=w;
 	}
 	for(int i=1;i<=n;i++) 
	{
  		dis[i]=G[1][i];
  		pre[i]=1;
 	}
 	v[1]=1;
 	pre[1]=0;
 	for(int j=1;j<=n-1;j++)
	{
  		long long minn=inf,x;
  		for(int i=1;i<=n;i++)
		{
   			if(v[i]==0&&dis[i]<minn)
			{
    			minn=dis[i];
    			x=i;
   			}
  		}
	  	v[x]=1;
	  	fulldis+=dis[x];
	  	vis[x][pre[x]]=vis[pre[x]][x]=1;
	  	for(int i=1;i<=n;i++)
		{
	   		if(v[i])
			{
	    		f[x][i]=f[i][x]=max(dis[x],f[i][pre[x]]);
	   		}
	   		if(v[i]==0&&G[x][i]<dis[i])
			{
	    		dis[i]=G[x][i];
	    		pre[i]=x;
	   		}
	  	}
 	}
	cout<<fulldis<<" ";
	long long ans=inf;
	for(int i=1;i<=n;i++)
	{
	  	for(int j=i+1;j<=n;j++)
		{
	   		if(vis[i][j]==0&&G[i][j]!=inf)
			{
	    		ans=min(ans,fulldis+G[i][j]-f[i][j]);
	   		}
	  	}
	}
	cout<<ans;
    return 0;
}```

玄关