P5060 Travel

$jjc$ really likes traveling ~~(smy)~~!

**$NOIP$ $2018$** has ended, and $jjc$ decided to travel around the country. Each place has many “big shots”. He has a map to help him plan a route from location $A$ to location $B$. The map has $N$ locations numbered from $1$ to $N$, and there are $M$ directed roads connecting different (or the same) locations. Now, $jjc$ already knows how many “big shots” he will meet when taking the $i$-th road directly from $u_i$ to $v_i$. He will write down the name of every “big shot” he meets (no matter whether the name has been written down before). However, each time he writes down one name, he needs to use one sticky note. Sticky notes are sold in bags, and each small bag that $jjc$ buys contains $P$ notes. $jjc$ does not want any sticky notes he buys to be wasted, so he wants every bag of notes he buys to be used up **exactly** when the trip ends. Besides that, $jjc$ is saving money for $......QwQ$, so he needs to spend less. Therefore, he wants this trip to use as few sticky notes as possible. However, he does not know how to find the best route. As one of the “big shots”, can you help $jjc$ solve this problem and find the optimal path that satisfies the conditions?

The first line contains five integers, in order: $N$, $M$, $P$, the index of the start point $A$, and the index of the end point $B$. Lines $2$ to $M+1$ describe the roads. Each line contains three integers: the start point index $u_i$ and end point index $v_i$ of the $i$-th road, and the number of “big shots” met on this road $num_i$.

If there exists a route that satisfies the conditions, output two lines. The first line contains one integer, the total number of “big shots” met on the chosen optimal path. The second line outputs the detailed route of the optimal path from $A$ to $B$. The testdata guarantees that the answer is unique. If no such route exists, output one line containing the string “$jjc$ $fails$ $in$ $travelling$” (without quotes).

This problem has $3$ subtasks. For $30\%$ of the testdata: $2 \le N \le 100$, $2 \le M \le 5000$, $1 \le P \le 50$. For another $20\%$ of the testdata: $2 \le N \le 5 \times 10^4$, $M \le 2 \times 10^5$, $P = 1$. For another $50\%$ of the testdata: $2 \le N \le 5 \times 10^4$, $M \le 2 \times 10^5$, $1 \le P \le 50$. For all testdata: $1 \le A, B, u_i, v_i \le N$, $0 \le num_i \le 10^8$. $By : $ Never Stop Learning. Translated by ChatGPT 5