Background

Little A had a nightmare.

Problem Description

Little A’s dreamland can be seen as an undirected graph with $n$ nodes and $m$ edges. Little A is at node $S$, a monster is at node $B$, and the safe house is at node $F$.

The monster is chasing Little A, and Little A needs to escape to the safe house. Little A realizes this is his own dream, so he can control it to some extent. He sets the monster’s moving speed to $3$, but the cost is that his own moving speed is set to $2$.

Little A will always walk along a shortest path to $F$. If there are multiple shortest paths, Little A will choose the one whose sequence of visited node indices in order is lexicographically smallest, because he thinks this makes it least likely to be caught.

The monster wanders in the dreamland. It moves randomly to a neighboring node, and it will not visit any node that it has already visited again.

Now Little A needs to know in the worst case whether he can safely reach the safe house, or when he will be caught by the monster.

Input Format

The first line contains five integers $n,m,S,B,F$.

The next $m$ lines each contain three integers $u_i,v_i,w_i$, meaning there is an undirected edge of length $w_i$ between $u_i$ and $v_i$.

Output Format

Two lines.

If Little A in the worst case can safely reach the safe house, output YES, and then on the next line output the distance from the monster to the safe house after Little A arrives at the safe house.

If Little A in the worst case cannot safely reach the safe house, output NO, and then on the next line output when Little A is caught by the monster.

If the answer on the second line is an integer, output the integer; otherwise output a decimal.

4 3 1 2 3
1 3 1
2 4 2
4 3 1

YES
1.5

4 3 1 2 3
1 3 2
2 4 2
4 3 1

NO
1

Hint

Explanation of “worst case”: The monster may have multiple possible ways to move. In other words, you need to consider every possible way the monster can move. As long as there exists some shortest-path movement strategy of the monster that can catch Little A, the answer is NO. The worst case means the monster chooses, among all its possible strategies, the one that can catch (or get close to) Little A the fastest.

Also, this problem does not have a special judge. That is, if the answer is an integer, you must output it exactly as an integer, without a decimal point. The testdata guarantees that there will be no answer with more than two decimal places.

Constraints

This problem uses bundled testcases.

$$\def\arraystretch{1.5} \begin{array}{c|c|c|c|c}\hline \textbf{~~Subtask~~}&\bm{~~n \le ~~}&\bm{~~~~m \le~~~~}& ~\textbf{~~Special Property~~}~&\textbf{~~Score~~}\cr\hline 0 &10 &20 & &10\cr\hline 1 &500 &1000 & &10\cr\hline 2 &800 &2000 & &10\cr\hline 3 &2\times10^5& &\text{A+B}&15 \cr\hline 4 &2\times10^5& &\text{A}&15 \cr\hline 5 &10^5 &2\times10^5& &20\cr\hline 6 &2\times10^5&2\times10^5& &20 \end{array}$$

Special property $\text{A}$: $m=n-1$.

Special property $\text{B}$: for each given $v_i$, it satisfies $v_i=u_i+1$.

For $100\%$ of the data, it is guaranteed that $S \ne B \ne F$ and $1 \le S,B,F \le n$, $1 \le w_i \le 10^3$, the graph is connected, and there are no multiple edges.

Special Scoring Method

This problem uses subtask dependencies, as follows:

• For subtasks $i\in\{0,3\}$, you only need to solve subtask $i$ correctly to obtain the score of subtask $i$.
• For subtask $4$, you need to solve subtask $3$ correctly to obtain the score of subtask $4$.
• For subtasks $i\in\{1,2,5,6\}$, you need to solve subtask $0$ correctly to obtain the score of subtask $i$.

Attachment Note

Since many contestants got stuck on sub3 during the contest, a set of testdata within sub3 is provided here to help you check and fix your code.

Translated by ChatGPT 5