Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,k;

int s,t;

#define MAXM 50010

#define MAXN 10010

#define MAXK 15

struct edge

{

	int to,nxt,v;

}e[(MAXM << 1) * MAXK * 2];

int edgenum = 0;

int lin[MAXN * MAXK] = {0};

inline void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int d[MAXN * MAXK];

bool v[MAXN * MAXK];

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	s = read();t = read();

	++s;++t;

	register int a,b,c;

	for(register int i = 1;i <= m;++i)

	{

		a = read();b = read();c = read();

		++a;++b;

		for(register int j = 0;j <= k;++j)

		{

			add(a + j * n,b + j * n,c);

			add(b + j * n,a + j * n,c);

		}

		for(register int j = 0;j < k;++j)

		{

			add(a + j * n,b + (j + 1) * n,0);

			add(b + j * n,a + (j + 1) * n,0);

		}

	}

	priority_queue<pair<int,int> > q;

	memset(d,0x3f,sizeof(d));

	d[s] = 0;

	q.push(make_pair(0,s));

	while(!q.empty())

	{

		register int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	int ans = 0x3f3f3f3f;

	for(register int i = 0;i <= k;++i)

	{

		ans = min(ans,d[t + i * n]);

	}

	printf("%d\n",ans);

	return 0;

}