#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<deque>
#include<stack>
 
using namespace std;
 
const int oo=~0u>>2;
 
struct edge
{
    int t,cost,sum;
    edge *next;
    edge(int _t,int _cost,int _sum,edge *_next):t(_t),cost(_cost),sum(_sum),next(_next){}
}*Map[101];
 
int N,M,K,dfn[101],low[101],lab[101],num,ind,S,T,tot;
bool vis[101];
stack<int>sta;
 
void addedge(int s,int t,int cost)
{
    Map[s]=new edge(t,cost,0,Map[s]);
}

void tarjan(int u)
{
    dfn[u]=low[u]=++ind;
    sta.push(u);
    vis[u]=true;
    for(edge *p=Map[u];p;p=p->next)
    {
        int t=p->t;
        if(!dfn[t])
        {
            tarjan(t);
            low[u]=min(low[u],low[t]);
        }
        else if(vis[t])
            low[u]=min(low[u],dfn[t]);
    }
    if(dfn[u]==low[u])
    {
        int t;
        tot++;
        do{
            t=sta.top();
            sta.pop();
            vis[t]=false;
            lab[t]=tot;
        }while(u!=t);
    }
}
 
void spfa()
{
    deque<int>deq;
	long long dist[101];
    for(int i=0;i<N;i++)
    {
        dist[i]=oo;
        vis[i]=false;
    }
    deq.push_back(S);
    dist[S]=0;
    while(!deq.empty())
    {
        int u=deq.front();
        deq.pop_front();
        vis[u]=false;
        for(edge *p=Map[u];p;p=p->next)
        {
            int sum=p->sum,t=p->t,cost=p->cost;
            if(lab[u]==lab[t])
            {
				if(Map[t])
					Map[t]->sum=sum;
				if(sum>K)
					cost=oo;
                if(dist[t]>dist[u]+cost)
                {
                    dist[t]=dist[u]+cost;
                    if(!vis[t])
                    {
                        vis[t]=true;
                        if(dist[t]<dist[u])
                            deq.push_front(t);
                        else
                            deq.push_back(t);
                    }
                }
            }
            else 
			{
				sum+=1;
				if(Map[t])
					Map[t]->sum=sum;
				if(sum>K)
					cost=oo;
				if(dist[t]>dist[u]+cost*2)
					dist[t]=dist[u]+cost*2;
                if(!vis[t])
                {
                    vis[t]=true;
                    if(dist[t]<dist[u])
                        deq.push_front(t);
                    else
                        deq.push_back(t);
                }
            }
        }
    }
    if(dist[T]<oo)
        printf("%d\n",dist[T]);
    else
        printf("-1\n");
}

void solve()
{
    for(int i=0;i<N;i++)
        if(!dfn[i])
            tarjan(i);
    spfa();
}

int main()
{
    freopen("travela.in","r",stdin);
    freopen("travela.out","w",stdout);
	while(true)
	{
		scanf("%d%d%d",&N,&M,&K);
		if(N==0&&M==0&&K==0)
			break;
		S=0;
		T=N-1;
		addedge(100,0,0);
		for(int i=1;i<=M;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			addedge(a,b,c);
		}
		solve();
		for(int i=0;i<N;i++)
		{
			dfn[i]=0;
			low[i]=0;
			vis[i]=false;
			if(Map[i])
				Map[i]->next=NULL;
			lab[i]=0;
		}
		ind=0;
		tot=0;
	}
    return 0;
}