#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define w first
#define to second
const int N = 3e6+5; 
int n, m, p;
int s, t;
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> q;
vector<pair<i64, int>> g[N];
stack<int> st;
i64 dis[N];
int pre[N];
bool vis[N];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> p >> s >> t;
	for(int i = 1; i <= m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back(make_pair(w, v + w % p * n));
	}
	for(int i = 1; i <= n; i++)
		for(auto j : g[i])
			for(int k = 1; k < p; k++){
				int arrive = (j.to + k * n) % (p * n);
				if( !arrive )	arrive += p * n;
				g[i + k * n].push_back(make_pair(j.w, arrive));
			}
	
	for(int i = 1; i <= p * n; i++)
		dis[i] = 1e18;
	q.push(make_pair(0, s));
	dis[s] = 0;
	while( !q.empty() ){
		pair<int, i64> h = q.top();
		q.pop();
		if( vis[h.to] )
			continue;
		vis[h.to] = 1;
		for(auto i : g[h.to]){
			if( dis[i.to] > dis[h.to] + i.w ){
				dis[i.to] = dis[h.to] + i.w;
				pre[i.to] = h.to;
				q.push(make_pair(dis[i.to], i.to));
			}
		}
	}
	if( dis[t] == 1e18 ){
		cout << "jjc fails in travelling";
		return 0;
	}
	cout << dis[t] << "\n";
	while( t ){
		st.push(t);
		t = pre[t];
	}
	while( !st.empty() ){
		if( st.top() > n ){
			st.top() %= n;
			if( !st.top() )
				st.top() = n;
		}
		cout << st.top();
		st.pop();
		if( !st.empty() )
			cout << "->";
	}
    return 0;
}