#include<fstream>
#include<vector>
#define inf 0x3f3f3f3f
#include<queue>
using namespace std;
int n,m,k;
struct nod
{
	long y,c;
};
vector<vector<nod> > mat(2001); 
vector<long> dist(2001,inf);
int main()
{
	ifstream fin("ubuntzei.in");
	ofstream fout("ubuntzei.out");
	fin>>n>>m;
	fin>>k;
	for(;m;--m)
	{
		int x,y,z;
		fin>>x>>y>>z;
		mat[x].push_back( (nod) {y,z} );
	}
	dist[1]=0;
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int x=q.front();
		for(int i=0;i<mat[x].size();++i)
			if( dist[x] + mat[x][i].c < dist[ mat[x][i].y ])
			{
				q.push(mat[x][i].y);
				dist[ mat[x][i].y ]= dist[x] + mat[x][i].c;
			}
		q.pop();
	}
	fout<<dist[n];
}