大臣的旅费

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 100000
int arr[100][100];
int n;
int f(int v0){	
	int s[100];
	int path[100];
	int dist[100];
	for(int i=0;i<n;i++){
		if(arr[v0][i]==INF){
			dist[i]=0;
		}else{
			dist[i]=arr[v0][i];
		}
		
		s[i]=0;
		if(dist[i]!=INF){
			path[i]=v0;
		}else{
			path[i]=-1;
		}
	}
	s[v0]=1;
	for(int i=1;i<n;i++){
		int MAX=0;
		int u=v0;
		for(int j=0;j<n;j++){
			if(dist[j]!=INF&&s[j]==0&&dist[j]>MAX){
				MAX=dist[j];
				u=j;
			}
		}
		//cout<<"MAX:"<<MAX<<"u:"<<u<<endl;
		s[u]=1;
		for(int j=0;j<n;j++){
			if(s[j]==0&&arr[j][u]!=INF&&arr[j][u]+dist[u]>dist[j]){
				dist[j]=arr[j][u]+dist[u];
				path[j]=u;
				//cout<<"path "<<j<<"="<<u<<endl;
			}
		}
	}
	int temp=0;
	for(int i=0;i<n;i++){
		if(dist[i]>temp){
			temp=dist[i];
		}
	}
	//cout<<"temp:"<<temp<<endl;
	return temp;
}
int main(){
	
	cin>>n;
	memset(arr,0,sizeof(arr));
	for(int i=1;i<n;i++){
		int x,y,v;
		cin>>x>>y>>v;
		arr[x-1][y-1]=v;
		arr[y-1][x-1]=v;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j){
				arr[i][j]=0;
			}else if(arr[i][j]==0){
				arr[i][j]=INF;
			}
		}
	}
	int temp=0;
	for(int i=0;i<n;i++){
		if(temp<f(i)){
			temp=f(i);
		}
	}
	int sum=0;
	for(int i=1;i<=temp;i++){
		sum+=(10+i);
	}
	cout<<sum;
	return 0;
}