I. The Auntie Whispers' Labyrinth
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Just as they thought they had unraveled the Whispering Tree's secret, the three stumbled into a bewildering section of the Unknown. Paths here were not just paths; they were shimmering, ethereal lines connecting various mystical intersections. Local lore, quickly recalled by Abd-Elmohaymen, stated this was "Auntie Whispers' Labyrinth," a place designed to keep lost souls within its bounds.

Their goal was to travel from their current location, Intersection $$$1$$$, to the rumored exit, Intersection $$$N$$$. Each street (path) connecting two intersections had a peculiar property: a given percentage chance of passing through it safely, without alerting the labyrinth's unseen guardians. To escape, they needed to find a path from Intersection $$$1$$$ to Intersection $$$N$$$ that offered the highest possible chance of reaching their destination without being caught.

Suddenly, a spectral whisper echoed through the labyrinth, and Adham, who had mysteriously rejoined their company after his earlier game with Halzoom, felt a strange surge of energy. "I $$$\cdots$$$ I can do something!" he exclaimed. "I can make one street in this labyrinth completely safe! A guaranteed passage!" This was their one boon: a single street they could render $$$100\ \%$$$ safe, meaning a guaranteed passage with no risk.

Sam07a, remembering the old tales of Auntie Whispers, realized this was their one opportunity. Omar quickly began mapping the intersections and their probabilistic connections. They needed to find the optimal path, deciding where to use Adham's unique power to maximize their chances of escape.

Help Sam07a, Omar, Abd-Elmohaymen, and Adham find the path that gives them the highest chance of escaping Auntie Whispers' Labyrinth safely.

Input

The first line contains two integers $$$n$$$ , $$$m$$$ ($$$1 \le n \le 10^5, n - 1 \le m \le \min(2 \cdot{10^5} , \ \frac{n\cdot(n - 1)}{2})$$$) the number of intersections and streets.

Then $$$m$$$ lines follow. The $$$i_{th}$$$ line contains $$$3$$$ integers $$$u_i$$$ , $$$v_i$$$ $$$(1 \leq u_i , v_i \leq n)$$$ and $$$p_i$$$ $$$(1 \leq p_i \leq 100)$$$ indicating a street between $$$u_i$$$ and $$$v_i$$$ with $$$p_i$$$ percentage chance of passing through it safely.

Output

Print the probability as a percentage with exactly $$$6$$$ digits after the decimal point. The percentage value is considered correct if it differs by at most $$$10^{-6}$$$ from the judge output.

Example
Input
5 7
1 4 85
2 3 70
2 5 100
3 5 80
1 2 50
3 4 90
3 1 70
Output
100.000000