#include<fstream>
#include<cmath>
#include<cstdlib>
#include<string>

using namespace std;

struct type
{
	long b,w,next;
};

long n,m,k,fi[51001];
long long f[51001][11];
type e[151001];

long long dfs(long x,long k)
{
	long long i,ls;
	long long ans,tmp;
	if(f[x][k]!=0)
		return f[x][k];
	if(x==n)
		return 0;
	i=fi[x];
	ans=0;
	while(i!=0)
	{
		ls=e[i].b;
		tmp=dfs(ls,k)+e[i].w;
		if(tmp>ans)
			ans=tmp;
		i=e[i].next;
	}
	if(k>0)
	{
		i=fi[x];
		while(i!=0)
		{
			ls=e[i].b;
			tmp=dfs(ls,k-1)+e[i].w;
			if(ans>tmp)
				ans=tmp;
			i=e[i].next;
		}
	}
	f[x][k]=ans;
	return ans;
}

int main()
{
	int i,x,y,z;
	ifstream fin("slide.in");
	ofstream fout("slide.out");
	fin>>n>>m>>k;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>z;
		e[i].b=y;
		e[i].w=z;
		e[i].next=fi[x];
		fi[x]=i;
	}
	fout<<dfs(1,k)<<endl;
	fin.close();
	fout.close();
	return 0;
}