题意：在权值和为p的路径下，选择最短的

使用分层图算法,dij

# 注意开longlong

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pr(x) pair<x,x>
#define up(i,j,k,l) for(int i=j;i<=k;i+=l)
#define down(i,j,k,l) for(int i=j;i>=k;i-=l)
using namespace std;
const int N=5e4+10,P=5e1+10,INF=1e18;
struct node{
	int b,c,e;
};
int n,m,p,s,t;
int u,v,w,hf,lt;
node td;
vector< pr(int) > vc[N];
priority_queue<node> q;
bool operator<(node x1,node x2)
{
	return x1.e>x2.e;
}
int d[N][P];
pr(int) l[N][P];
vector<int> ans;
bool f[N][P];
void dij()
{
	q.push({s,0,0});
	up(i,0,N-1,1){
		up(j,0,P-1,1){
			d[i][j]=INF;
		}
	}
	d[s][0]=0;
	while(!q.empty()){
		td=q.top();
		q.pop();
		if(f[td.b][td.c]==true){
			continue;
		}
		f[td.b][td.c]=true;
		for(auto fw:vc[td.b]){
			hf=(td.c+fw.second)%p;
			if(f[fw.first][hf]==false && d[fw.first][hf]>d[td.b][td.c]+fw.second){
				d[fw.first][hf]=d[td.b][td.c]+fw.second;
				l[fw.first][hf].first=td.b;
				l[fw.first][hf].second=td.c;
				q.push({fw.first,hf,d[fw.first][hf]});
			}
		}
	}
	return;
}
void sc(int g,int k)
{
	if(g==0){
		return;
	}
	ans.push_back(g);
	sc(l[g][k].first,l[g][k].second);
	return;
}
void solve()
{
	cin>>n>>m>>p>>s>>t;
	up(i,1,m,1){
		cin>>u>>v>>w;
		vc[u].push_back({v,w});
	}
	dij();
	if(d[t][0]==INF){
		puts("jjc fails in travelling");
	}
	else{
		cout<<d[t][0]<<endl;
		sc(t,0);
		reverse(ans.begin(),ans.end());
		lt=ans.back();
		ans.pop_back();
		for(auto fw:ans){
			cout<<fw<<"->";
		}
		cout<<lt<<endl;
	}
	return;
}
signed main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int _=1;
	//cin>>_;
	up(i,1,_,1){
		solve();
	}
	return 0;
}##