谢谢dalao QAQ

#include<bits/stdc++.h>
#define re register
#define il inline
#define MAXN 10005
#define MAXM 50005
#define MAXK 25
#define MAX 1983721205
#define fup(i,a,b) for(re int i = a;i <= b;i ++)
#define fedge(i,x) for(re int i = head[x];i;i = e[i].nxt)
#define fin(a)  freopen(#a".in","r",stdin)
#define fout(a) freopen(#a".out","w",stdout)

using namespace std;

int head[9999999],dis[9999999];
bool vis[9999999];
int cnt = 0;
int N,M,K;

il int read()
{
	int w = 0,x = 0;
	char ch = 0;
	
	while(!isdigit(ch))
	{
		w |= ch == '-';
		ch = getchar();
	}
	
	while(isdigit(ch))
	{
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	
	return w ? -x : x;
}

il void write(int x)
{
	if(x < 0)
	{
		x = -x;
		putchar('-');
	}
	
	if(x > 9)
		write(x / 10);
		
	putchar(x % 10 + '0');
}

struct edge
{
	int nxt,to,w;
}e[9999999];

il void add(int u,int v,int w)
{
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

struct node
{
	int num,d;
	bool operator <(const node b)const
	{
		return d>b.d;
	}
};

il void DJ(int s)
{
	memset(dis,0x3f,sizeof(dis));
	
	dis[s]=0;
	priority_queue<node> q;
	
	q.push((node){s,0});
	int u,v;
	while(!q.empty())
	{
		u=q.top().num;q.pop();
		if(vis[u])continue;vis[u]=1;
		fedge(i,u)
		{
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				q.push((node){v,dis[v]});
			}
		}
	}
}



int main()
{
	fin(P2939);
	fout(P2939);
	
	N = read();M = read();K = read();
	
	
	fup(i,1,M)
	{
		int u = read(),v = read(),w = read();
		
		add(u,v,w);
		add(v,u,w);
		
		fup(j,1,K)
		{
			add(u + N * (j - 1),v + N * j,0);//straight
			
			add(u + N * j,v + N * j,w);
			add(v + N * j,u + N * j,w);//forward
		}
	}
	
	DJ(1);
	
	write(dis[N * K + N]);
	
	return 0;
}