#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=101;
const int MAXM=100001;
const int MAXK=11;
typedef vector<int> Vec;
stack<int> S; 
bool InStack[MAXN];
int times[MAXN][MAXN];
Vec Map[MAXN];
int dfn[MAXN],low[MAXN];
int flag[MAXK][MAXN];
int dist[MAXK][MAXN];
int Index=0,N,M,K;

inline int Min(int a,int b) {return a<b?a:b;}

inline void init()
{
	scanf("%d %d %d\n",&N,&M,&K);
	
	if(N==1)
	{
		printf("0\n");
		exit(0);
	}
	
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			times[i][j]=-1;
	
	int u,v,w;
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d %d\n",&u,&v,&w);
		u++,v++;
		if(times[u][v]==-1)
		{
			times[u][v]=2*w;
			Map[u].push_back(v);
			continue;
		}
		if(times[u][v]>2*w)
			times[u][v]=2*w;
	}
}

void Tarjan(int u)
{
    dfn[u]=low[u]=++Index;
    S.push(u);
    InStack[u]=1;
    int v;
    for(unsigned int i=0;i<Map[u].size();i++)
    {
        v=Map[u][i];
        if(dfn[v]==0)
        {
            Tarjan(v); low[u]=Min(low[u],low[v]);
        }
        else if(InStack[v]) low[u]=Min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
		int Tmp,Top=0,Num[MAXN];
        do
        {
            Tmp=S.top();
            S.pop();
            InStack[Tmp]=0;
			Num[++Top]=Tmp;
        }while(u!=Tmp);
		
		for(int i=1;i<=Top;i++)
		{
			for(int j=1;j<=Top;j++)
			{
				if(i==j) continue;
				if(times[i][j]==-1) continue;
				times[i][j]/=2;
			}
		}
    }
}

const int INF=~0u>>2;

class QUEUE
{
public:
	int k,u;
};

queue<QUEUE> q;

inline void SPFA()
{
	for(int i=1;i<=N;i++)
		for(int j=1;j<=K;j++)
			dist[j][i]=INF,
			flag[j][i]=0;
	dist[0][1]=0; flag[0][1]=1;
	q.push((QUEUE){0,1});
	
	int u,v,k,c;
	QUEUE tmp;
	while(q.size())
	{
		tmp=q.front(); q.pop();
		u=tmp.u; k=tmp.k;  flag[k][u]=0;
		if(k==K) continue;
		for(unsigned int i=0;i<Map[u].size();i++)
		{
			v=Map[u][i];
			c=dist[k][u]+times[u][v];
			if(c>=dist[k+1][v]) continue;
			dist[k+1][v]=c;
			if(flag[k+1][v]) continue;
			flag[k+1][v]=1;
			q.push((QUEUE){k+1,v});
		}
	}
	int ans=INF;
	for(int i=K;i>=1;i--)
		ans=Min(ans,dist[i][N]);
	if(ans==INF) printf("-1\n");
	else printf("%d\n",ans);
}

int main()
{
	freopen("travela.in","r",stdin);
	freopen("travela.out","w",stdout);
	init();
	Tarjan(1);
	SPFA();
	return 0;
}