看起来数组没开出问题，#9莫名其妙的WA了

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 10000
#define maxm 50000
#define maxk 10
#define inf 2100000000

struct inside {
	int a, b, c;
} a[maxm + 10];
struct side {
	int l, t;
} x;
std :: vector <side> S[maxn * (maxk + 1) + 10];
int n, m, k, s, t;

int ll[maxn * (maxk + 1) + 10];
int len[maxn * (maxk + 1) << 2];
int vis[maxn * (maxk + 1) + 10];

inline void build(int i, int l, int r) {
	if (l == r) {
		len[i] = ll[l];
		return;
	}
	int mid = l + r >> 1, ls = i << 1, rs = (i << 1) + 1;
	build(ls, l, mid), build(rs, mid + 1, r);
	len[i] = std :: min(len[ls], len[rs]);
	return;
}

inline int findmin(int i, int l, int r) {
	//printf("find : %d %d %d %d\n", i, l, r, len[i]);
	if (l == r) {
		ll[l] = len[i];
		return l;
	}
	int mid = l + r >> 1, ls = i << 1, rs = (i << 1) + 1;
	if (len[ls] < len[rs]) return findmin(ls, l, mid);
	else return findmin(rs, mid + 1, r);
}

inline void push(int i, int l, int r, int wh, int num) {
	if (l == r) {
		len[i] = num;
		return;
	}
	int mid = l + r >> 1, ls = i << 1, rs = (i << 1) + 1;
	if (wh <= mid) push(ls, l, mid, wh, num);
	else push(rs, mid + 1, r, wh, num);
	len[i] = std :: min(len[ls], len[rs]);
	return;
}

inline void dijkstra() {
	for (int i = 0; i < n; i++)
		ll[i] = inf;
	for (int i = 0, maxi = S[s].size(); i < maxi; i++)
		ll[S[s][i].t] = S[s][i].l;
	build(1, 0, n - 1);
	ll[s] = 0, vis[s] = 1;
	for (int i = 1; i < n; i++) {
		int now = findmin(1, 0, n - 1); 
		if (vis[now]) break;
		//printf("now : %d\n", now);
		vis[now] = 1;
		push(1, 0, n - 1, now, inf);
		for (int j = 0, maxj = S[now].size(); j < maxj; j++)
			if (!vis[S[now][j].t] && S[now][j].l + ll[now] < ll[S[now][j].t]) 
			    ll[S[now][j].t] = S[now][j].l + ll[now],
			    push(1, 0, n - 1, S[now][j].t, ll[S[now][j].t]);
		/*for (int i = 0; i < n; i++)
			printf("%d %d\n", i, ll[i]);
		putchar('\n');*/
	}
	return;
}

inline int cmp(inside x, inside y) {
	if (x.a != y.a) return x.a < y.a;
	if (x.b != y.b) return x.b < y.b;
	return x.c < y.c;
}

int main(void) {
	freopen("in.in", "r", stdin);
	scanf("%d %d %d\n%d %d", &n, &m, &k, &s, &t);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a[i].a, &a[i].b, &a[i].c);
		if (a[i].a > a[i].b) std :: swap(a[i].a, a[i].b);
	}
	std :: sort(a + 1, a + m + 1, cmp);
	a[0].a = -1;
	for (int i = 1; i <= m; i++) {
		if (a[i].a == a[i - 1].a && a[i].b == a[i - 1].b) continue;
		//printf("Side : %d to %d length %d\n", a[i].a, a[i].b, a[i].c);
		for (int j = 0; j < k; j++) {
			x.l = a[i].c;
			x.t = a[i].b + j * n, S[a[i].a + j * n].push_back(x);
			x.t = a[i].a + j * n, S[a[i].b + j * n].push_back(x);
			x.l = 0;
			x.t = a[i].b + (j + 1) * n, S[a[i].a + j * n].push_back(x);
			x.t = a[i].a + (j + 1) * n, S[a[i].b + j * n].push_back(x);
		}
		x.l = a[i].c;
		x.t = a[i].b + k * n, S[a[i].a + k * n].push_back(x);
		x.t = a[i].a + k * n, S[a[i].b + k * n].push_back(x);
	}
	t = t + n * k, n *= (k + 1);
	/*for (int i = 0; i < n; i++)
		for (int j = 0, maxj = S[i].size(); j < maxj; j++)
			printf("S[%d][%d] = %d\n", i, S[i][j].t, S[i][j].l);*/
	dijkstra();
	/*for (int i = 0; i < n; i++)
		printf("%d %d\n", i, ll[i]);
	putchar('\n');*/
	printf("%d\n", ll[t]);
	return 0;
}