C. Chaotic Crossing
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Public domain, SVG by Bouwe Brouwer on Wikimedia Commons

You just arrived at the train station in Leiden, and you would like to walk to the location of the BAPC. However, exiting the station, you encounter a massive intersection with cars, buses, trams, and bicycles coming from all directions! Since the BAPC is at the other side of this intersection, you need to find a safe way to cross. The intersection consists of $$$n$$$ patches of pavement where you can safely stand still and $$$m$$$ bidirectional zebra crossings. Each zebra crossing has its own traffic light: you can only walk across it when the light is green. Each second, you can either wait on the patch of pavement you are standing on, or you can walk across any connected zebra crossing where the light is currently green. The traffic lights behave randomly: each traffic light has a parameter $$$p$$$, and each second, the traffic light is green with probability $$$p$$$, and red with probability $$$1-p$$$, completely independently from all other traffic lights.

Since you want to be on time for the BAPC, you want to figure out the minimal expected time needed to cross the intersection, starting from the train station. The train station is located next to the pavement patch numbered $$$1$$$, and you need to go to the pavement patch numbered $$$n$$$.

Input

The input consists of:

  • One line with two integers $$$n$$$ and $$$m$$$ ($$$2\leq n \leq {2\cdot 10^5}$$$, $$$1 \leq m \leq {4 \cdot 10^5}$$$), the number of patches of pavement and the number of zebra crossings.
  • $$$m$$$ lines, each containing three integers $$$u$$$, $$$v$$$, and $$$p$$$ ($$$1\leq u \lt v \leq n$$$, $$$1\leq p \leq 100$$$), indicating that there is a bidirectional zebra crossing between patch $$$u$$$ and patch $$$v$$$, with a $$$p\%$$$ chance of being green each second.
There is at most one zebra crossing between each pair of patches of pavement.
Output

Output the expected time to cross the intersection. If you cannot reach the BAPC, output "impossible".

Your answer should have an absolute or relative error of at most $$$10^{-6}$$$.

Examples
Input
2 1
1 2 50
Output
2
Input
4 4
1 4 1
1 2 80
2 3 90
3 4 70
Output
3.754898468
Input
4 5
1 2 50
1 3 50
2 3 90
2 4 33
3 4 67
Output
3.007172
Input
3 1
1 2 100
Output
impossible