106 miles to Chicago

Input

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

Each of the next $m$ lines describes a street with three integers $a$, $b$, and $p$ (1 \le a, b \le n, a \ne b, 1 \le p \le 100): $a$ and $b$ are the endpoints of the street, and $p$ is the probability (in percent) that the Blues Brothers can pass along this street without being caught. Each street is bidirectional, and there is at most one street between any pair of intersections.

Output

Calculate the probability of the safest path from intersection $1$ (the Palace Hotel) to intersection $n$. You may assume that there is at least one path between intersection $1$ and $n$.

Print this probability as a percentage with exactly $6$ digits after the decimal point, in the format shown below.

Examples

Note

The safest path for the sample input is 1 \to 4 \to 3 \to 5.