3221225477

#include<bits/stdc++.h>
#define NOC ios::sync_with_stdio(0);cin.tie();cout.tie();
#define up(a,b) for(int i=a;i<=b;i++)
#define dn(a,b) for(int i=a;i>=b;i--)
using namespace std;
struct node
{
	int y;
	int z;
};
vector<node>g[2505];
queue<int>q;
int m,dis[2505],v[2505];
int alpha(int x)
{
	if('A'<=x&&x<='Z')
	{
		x=x-'A'+1;
	}
	if('a'<=x&&x<='z')
	{
		x=x-'a'+27;
	}
	return x;
}
void spfa(int s)
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push(s);
	v[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		v[x]=0;
		for(int j=0;j<g[x].size();j++)
		{
			int y=g[x][j].y;
			if(dis[y]>dis[x]+g[x][j].z)
			{
				dis[y]=dis[x]+g[x][j].z;
				q.push(y);
				v[y]=1;
			}
		}
	}
}
int main(){
	NOC;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		g[x].push_back((node){y,z});
		g[y].push_back((node){x,z});
	}
	spfa(alpha('Z'));
	sort(dis+1,dis+m+1);
	cout<<dis[m];
	return 0;
}