#include<stdio.h>
#include<string.h>
#include<queue>

using namespace std;

struct orz
{
	int a,b;
};

int n,m,K;

int s[101],u[101][101],v[101][101];

queue <orz> q;

int main()
{
	freopen("travela.in","r",stdin);
	freopen("travela.out","w",stdout);
	int i,j,k,x,y,z;
	for(scanf("%d%d%d",&n,&m,&K);n|m|K;scanf("%d%d%d",&n,&m,&K))
	{
		memset(v,0,sizeof(v));
		memset(u,60,sizeof(u));
		memset(s,60,sizeof(s));
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			x++;y++;
			u[x][y]=1;
			if(v[x][y]==0||v[x][y]>z)
				v[x][y]=z;
		}
		for(i=1;i<=n;i++)
			u[i][i]=0;
		for(k=1;k<=n;k++)
		{
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=n;j++)
				{
					if(u[i][k]+u[k][j]<u[i][j])
						u[i][j]=u[i][k]+u[k][j];
				}
			}
		}
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if((u[i][j]>1000000000)||(u[j][i]>1000000000))
					v[i][j]<<=1;
			}
		}
		s[1]=0;
		orz tmp;
		tmp.a=1;tmp.b=0;
		q.push(tmp);
		while(!q.empty())
		{
			tmp=q.front();
			for(i=1;i<=n;i++)
			{
				if(v[tmp.a][i]&&v[tmp.a][i]+s[tmp.a]<s[i])
				{
					if(u[tmp.a][i]>1000000000||u[i][tmp.a]>1000000000)
					{
						if(tmp.b+1<=K)
						{
							s[i]=v[tmp.a][i]+s[tmp.a];
							orz tmp1;
							tmp1.a=i;
							tmp1.b=tmp.b+1;
							q.push(tmp1);
						}
					}
					else
					{
						s[i]=v[tmp.a][i]+s[tmp.a];
							orz tmp1;
							tmp1.a=i;
							tmp1.b=tmp.b;
							q.push(tmp1);
					}
				}
			}
			q.pop();
		}
		if(s[n]>1000000000)
			printf("-1\n");
		else
			printf("%d\n",s[n]);
	}
	return 0;
}