10263: CF EDU - Binary Search - Step 4 - B. Minimum Average Path
[Creator : ]
Description
The road network consists of $n$ junctions and $m$ one-way roads, with each road leading from a lower-numbered junction to a higher-numbered junction. Each road has a number. Your task is to find a path from junction 1 to junction $n$ at which the arithmetic mean of the numbers corresponding to the edges is minimal possible.
Input
The first line contains integers $n,m\ (2≤n≤10^5,\ 1≤m≤10^5)$.
The next $m$ lines contain triples of numbers $a_i, b_i, c_i\ (1≤a_i<b_i≤n,\ 0≤c_i≤100)$, which means that there is a road leading from the junction $a_i$ to the junction $b_i$, which corresponds to the number $c_i$. For each pair of junction, there is at most one road that connects them. It is guaranteed that there is a path from junction $1$ to junction $n$.
The next $m$ lines contain triples of numbers $a_i, b_i, c_i\ (1≤a_i<b_i≤n,\ 0≤c_i≤100)$, which means that there is a road leading from the junction $a_i$ to the junction $b_i$, which corresponds to the number $c_i$. For each pair of junction, there is at most one road that connects them. It is guaranteed that there is a path from junction $1$ to junction $n$.
Output
On the first line print the number of edges in the selected path $k$.
On the next line print $k+1$ integers, indices of junctions visited by the selected path.
On the next line print $k+1$ integers, indices of junctions visited by the selected path.
Sample 1 Input
4 3
1 2 1
2 3 0
2 4 1
Sample 1 Output
2
1 2 4
Sample 2 Input
3 3
1 2 1
2 3 2
1 3 1
Sample 2 Output
1
1 3