Problem Background

$jjc$ loves traveling(smy)!

Problem Description

$NOIP$ $2018$ has concluded, and $jjc$ decides to travel across the country, where each place is home to many experts. He has a map to help him plan a route from location $A$ to location $B$. The map contains $N$ locations numbered from $1$ to $N$, and $M$ directed roads connecting different (or the same) locations.

Now, $jjc$ knows how many experts he will encounter on the $i$-th road from location $u_i$ to location $v_i$, and he will record the name of each expert he meets (regardless of whether he has recorded them before). However, recording each name requires a sticky note, which is sold in packs of $P$ notes. $jjc$ does not want to waste any notes, so he hopes that each pack he buys will be used up exactly. Additionally, $jjc$ is saving money for... $QwQ$, so he wants to minimize his consumption of notes during this trip.

However, he doesn't know how to find the most suitable path. As one of the experts, can you help $jjc$ solve this problem and find the best path that meets the conditions?

Input Format

The first line contains five integers: $N$, $M$, $P$, the starting location $A$, and the ending location $B$.

From the second line to the $M+1$-th line, each line describes the information of a road with three integers: the starting location $u_i$, the ending location $v_i$, and the number of experts $num_i$ encountered on this road.

Output Format

If a path meeting the conditions exists, output two lines: the first line contains an integer representing the total number of experts encountered on the chosen path, and the second line outputs the detailed route from location $A$ to location $B$. The answer is guaranteed to be unique.

If no such path exists, output a single line containing the string "$jjc$ $fails$ $in$ $travelling$".

Sample Input and Output

Sample Input #1

2 2 3 1 2
1 2 1
2 2 1

Sample Output #1

3
1->2->2->2

Sample Input #2

4 6 3 2 3
2 1 7
2 4 0
4 3 6
1 4 0 
2 3 1
2 3 9

Sample Output #2

6
2->4->3

Sample Input #3

3 3 5 1 3
1 2 15
2 3 7
1 3 3 

Sample Output #3

jjc fails in travelling

Notes

This problem has $3$ Subtasks.

For $30\%$ of the data, $2≤N≤100$, $2≤M≤5000$, $1≤P≤50$.

For another $20\%$ of the data, $2≤N≤5×10^4$, $M≤2×10^5$, $P=1$.

For another $50\%$ of the data, $2≤N≤5×10^4$, $M≤2×10^5$, $1≤P≤50$.

For all data, $1≤A,B,u_i,v_i≤N$, $0≤num_i≤10^8$.

$By :$ 学无止境

见题面 Input 部分

见题面 Output 部分