rt 照着题解打的 不知道自己打就一直mle

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int idx = 0;
int n, m, p, s, t;int h;
int ans[5010000];int head[5010000];
bool vis[5010000];int fa[5010000];
long long dis[5010000];
struct edge {
	int v;
	long long  w;
	int next;
};
edge e[10001000];
struct node {
	long  long   dis;
	int  u;
	node () {}
	node (long long dis1, int  u1) : dis(dis1), u(u1) {}
	bool operator < (const node &qw)  const {
		return dis > qw.dis;
	}
};
void add(int u, int v, long long  w) {
	e[++idx] = {v, w, head[u]};
	head[u] = idx;
}
priority_queue<node>q;
void dij() {
	dis[s] = 0;
	q.push((node) {
		0, s
	});
	while (!q.empty()) {
		auto lte = q.top();
		q.pop();
		int u = lte.u;
		if (vis[u])continue;
		vis[u] = 1;
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if (!vis[v]&&dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				fa[v] = u;
				q.push((node) {
					dis[v], v
				});
			}
		}
	}
}
void print(int rt) {
	if (rt == 0)	return ;
	if (rt % n != 0)	ans[++h] = rt % n;
	else 	 ans[++h] = n;
	print(fa[rt]);
}
void solve() {
	scanf("%d %d %d %d %d", &n, &m, &p, &s, &t);
	int a,b;
	long long c;
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %lld", &a, &b, &c);
		for (int j = 0; j < p; j++)
			add(j * n + a, (c + j) % p * n + b, c);
	}
	memset(dis,0x7f7f7f7f, sizeof dis);
	dij();
	if (dis[t] !=9187201950435737471 ) {
		printf("%lld\n", dis[t]);
		print(t);
		for (int i = h; i >= 2; i--) {
			printf("%d->", ans[i]); //输出
		}
		printf("%d\n", ans[1]);
	} else printf("jjc fails in travelling\n");
}
int main() {
	solve();
	return 0;
}