#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#define N 110
using namespace std;
ifstream in("travela.in");
ofstream out("travela.out");
int n,m,K;
int dfn[N]={0},low[N]={0};
int tim=0;
vector<int > G[N],C[N];
bool l[N]={0};
int f[N][N]={0};
int s[N]={0},cnt=0;
int color[N]={0};
int INF=(1<<28);
void tarjan(int u)
{
	int i,v;
	dfn[u]=low[u]=++tim;
	l[u]=1;
	s[++s[0]]=u;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(l[v])low[u]=min(low[u],dfn[v]);
		
	}
	if(dfn[u]==low[u])
	{
		cnt++;
		do
		{
			v=s[s[0]];
			l[v]=0;
		    color[v]=cnt;
			s[0]--;
		}while(u!=v);
	}
}
void SPFA(int s)
{
	int i,j,u,v,w,temp;
	queue<int> q;
	for(i=1;i<=n;i++)
	{
		l[i]=0;
		for(j=0;j<=100;j++)
		{
			f[j][i]=INF;
		}
	}
	for(j=0;j<=K;j++)f[j][s]=0;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		l[u]=0;
		for(i=0;i<G[u].size();i++)
		{
			v=G[u][i];
			w=C[u][i];
			if(color[u]!=color[v])
			{
				w=w<<1;
			    for(j=0;j<=K;j++)
			    {
				    temp=f[j][u]+w;
				    if(f[j+1][v]>temp)
				    {
					    f[j+1][v]=temp;
					    if(!l[v])
					    {
						    l[v]=1;
						    q.push(v);
					    }
				    }
			    }
			}
			else
			{
				for(j=0;j<=K;j++)
			    {
				    temp=f[j][u]+w;
				    if(f[j][v]>temp)
				    {
					    f[j][v]=temp;
					    if(!l[v])
					    {
						    l[v]=1;
						    q.push(v);
					    }
				    }
			    }
			}
		}
	}
}
void work()
{
	int i,ans=INF;
	SPFA(1);
	for(i=0;i<=K;i++)ans=min(ans,f[i][n]);
	//for(i=1;i<=n;i++)out<<color[i]<<endl;
	if(ans!=INF)out<<ans<<endl;
	else out<<-1<<endl;
}
void read()
{
	int i,u,v,w;
	in>>n>>m>>K;
	for(i=1;i<=m;i++)
	{
		in>>u>>v>>w;
		u++;v++;
		G[u].push_back(v);
		C[u].push_back(w);
	}
	for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
}
void clear()
{
	int i,j;
	for(i=1;i<=100;i++)
	{
		G[i].clear();
		C[i].clear();
		for(j=0;j<=15;j++)
		{
			f[j][i]=0;
		}
		l[i]=0;
		dfn[i]=low[i]=0;
		tim=cnt=0;
		color[i]=0;
	}
}
int main()
{
	while(true)
	{
		
		clear();
	    read();
		if(!n)break;
	    work();
	}
	
	return 0;
}