#include <cstdio>
#include <climits>

#define I_F "travela.in"
#define O_F "travela.out"

const short MAXn=100;
const short MAXk=10+1;

struct map
{
	short x;
	int s;
	bool f;
	map *next;
};
struct que
{
	short x,k;
	que *next;
};

short n, k;
int m;
bool fmap[MAXn][MAXn];
int smap[MAXn][MAXn];
long d[MAXn][MAXk];
bool p[MAXn][MAXk];
map* s[MAXn]={NULL};
long ans;

void Prework();
void Input();
void Floyd();
void Getmap();
void Spfa();
void Output();

int main()
{
	freopen(I_F,"r",stdin);
	freopen(O_F,"w",stdout);
	Prework();
	Input();
	while (n+m+k>0)
	{
		Floyd();
		Getmap();
		Spfa();
		Output();
		Prework();
		Input();
	}
	return 0;
}

void Prework()
{
	map *t;
	for (short i=0; i<MAXn; ++i)
		while (s[i]!=NULL)
		{
			t=s[i];
			s[i]=s[i]->next;
			delete t;
		}
	for (short i=0; i<MAXn; ++i)
		for (short j=0; j<MAXn; ++j)
			fmap[i][j]=false,
			smap[i][j]=0;
	for (short i=0; i<MAXn; ++i)
		fmap[i][i]=true;
	for (short i=0; i<MAXn; ++i)
		for (short j=0; j<MAXk; ++j)
			d[i][j]=LONG_MAX/2,
			p[i][j]=false;
	d[0][0]=0;
	ans=LONG_MAX/2;;
}

void Input()
{
	short a,b;
	int t;
	scanf("%hd%d%hd",&n,&m,&k);
	for (int i=0; i<m; ++i)
	{
		scanf("%hd%hd%d",&a,&b,&t);
		fmap[a][b]=true;
		if (t<smap[a][b] || smap[a][b]==0)
			smap[a][b]=t;
	}
}

void Floyd()
{
	for (short k=0; k<n; ++k)
		for (short i=0; i<n; ++i)
			for (short j=0; j<n; ++j)
				fmap[i][j]=fmap[i][j] || (fmap[i][k] && fmap[k][j]);
}

void Getmap()
{
	map *t;
	for (short i=0; i<n; ++i)
		for (short j=0; j<n; ++j)
			if (smap[i][j]>0)
			{
				t=s[i];
				s[i]=new map;
				s[i]->x=j;
				s[i]->f=fmap[j][i];
				s[i]->s=(s[i]->f)?smap[i][j]:smap[i][j]*2;
				s[i]->next=t;
			}
}

void Spfa()
{
	que *head, *tail, *temp;
	head=new que;
	head->x=head->k=0;
	head->next=NULL;
	tail=head;
	p[0][0]=true;
	short tk;
	while (head!=NULL)
	{
		for (map *i=s[head->x]; i!=NULL; i=i->next)
		{
			tk=(i->f)?head->k:head->k+1;
			if (tk<=k && d[head->x][head->k]+i->s<d[i->x][tk])
			{
				d[i->x][tk]=d[head->x][head->k]+i->s;
				if (p[i->x][tk]==false)
				{
					p[i->x][tk]=true;
					tail->next=new que;
					tail=tail->next;
					tail->x=i->x;
					tail->k=tk;
					tail->next=NULL;
				}
				if (i->x==n-1)
					ans=(d[i->x][tk]<ans)?d[i->x][tk]:ans;
			}
		}
		temp=head;
		head=head->next;
		p[temp->x][temp->k]=false;
		delete temp;
	}
}

void Output()
{
	printf("%ld\n",ans);
}