#include <iostream> 
#include <cmath> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <cstdlib> 
#include <iomanip> 
#include <set> 
#include <algorithm> 
#define MAXN 0x7fffffff 
using namespace std; 
int a[1001][1001][2],b,c,d,l,m=1,m1,m2,m3,n[1001],r[1001],s,k[1001][2],z[1001][12],h=1,t,p[10000000][2];
void DFS(int x)
{
    int y;
    r[x]=1;
    k[x][0]=m;
    k[x][1]=m;
    m++;
    n[m3]=x;
    m3++;
    for (y=0;y<b;y++)
    {
        if (a[x][y][0]==0) continue;
        if (k[y][0]==0) 
        {
            DFS(y);
            if (k[y][1]<k[x][1]) k[x][1]=k[y][1];
        }
            else if (r[y]==1) k[x][1]=k[y][0]<k[x][1]?k[y][0]:k[x][1]; 
    }
    if (k[x][0]==k[x][1])
    {
        int i;
        i=n[m3-1];
        while (i!=x)
        {
            r[i]=0;
            m3--;
			a[i][n[m3-1]][1]++;
			a[n[m3-1]][i][1]++;
            i=n[m3-1];
        }
        m3--;
        r[x]=0;
    }
}
void SPFA(void)
{
	bool bo[101][11]={false};
	int i,j;
	while (h>t)
    {
        bo[p[t][0]][p[t][1]]=false;
        for (i=0;i<b;i++)
			for (j=0;j<=d;j++)
				if (p[t][0]!=i)
				{
					if ((a[p[t][0]][i][1]==1)&&(z[p[t][0]][j]<z[i][j]-a[p[t][0]][i][0]))
					{
						if (a[p[t][0]][i][0]!=0) 
						{
							z[i][j]=z[p[t][0]][j]+a[p[t][0]][i][0];
							if (bo[i][j]==false) 
							{
								bo[i][j]=true;
								p[h][0]=i;
								p[h][1]=j;
								h++;
							}
						}
					}
					if ((a[p[t][0]][i][1]==0)&&(z[p[t][0]][j]<z[i][j+1]-a[p[t][0]][i][0]*2))
					{
						if (a[p[t][0]][i][0]!=0)
						{
							z[i][j+1]=z[p[t][0]][j]+a[p[t][0]][i][0]*2;
							if (bo[i][j]==false) 
							{
								bo[i][j]=true;
								p[h][0]=i;
								p[h][1]=j;
								h++;
							}
						}
					}
				}
        t++;
    }
}
int main(void) 
{    
    freopen("travela.in","r",stdin); 
    freopen("travela.out","w",stdout); 
	scanf("%d%d%d",&b,&c,&d);
	for (l=0;l<c;l++)
	{
		scanf("%d%d",&m1,&m2);
		scanf("%d",&s);
		if (a[m1][m2][0]==0) a[m1][m2][0]=s;
			else if (s<a[m1][m2][0]) a[m1][m2][0]=s;
	}
	for (l=0;l<b;l++)
		if (r[l]==0) DFS(l);
	for (l=0;l<b;l++)
		for (m1=0;m1<=d;m1++)
			z[l][m1]=MAXN;
	z[0][0]=0;
	SPFA();
	s=MAXN;
	for (l=0;l<=d;l++)
		if (z[b-1][l]<s) s=z[b-1][l];
	if (s==MAXN) printf("-1");
		else printf("%d",s);
	fclose(stdin); 
    fclose(stdout); 
    return 0; 
}