#include<bits/stdc++.h>
using namespace std;
const int N =6000;
int n,m,s;
int a[N][N];
void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
		}
	}
}
int main()
{
	memset(a,0x3f,sizeof(a));
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		cin>>a[u][v];
	}
	floyd();
	int maxx=-1e6-10;
	for(int i=1;i<=n;i++)
	{
		if(i!=m)
			maxx=max(maxx,a[i][m]+a[m][i]);
	}
	cout<<maxx<<endl;
	return 0;
}