106 Miles to Chicago

In the movie The Blues Brothers, the orphanage where Elwood and Jake grew up will be sold to the Board of Education unless they pay $5000 in back taxes to the Cook County Assessor's Office in Chicago. After earning that money by playing a gig in the Palace Hotel ballroom, they have to find a way to Chicago.

This is not as easy as it sounds: they are chased by the police, a country band, and a group of Nazis. On top of that, it is 106 miles to Chicago, it is dark, and they are wearing sunglasses.

Since they are on a mission from God, help them find the safest route to Chicago. Here, the safest route is the one that maximizes the probability of not being caught.

The input contains several test cases.

Each test case begins with two integers $n$ and $m$ ($2 \le n \le 100$, $1 \le m \le n(n-1)/2$), where $n$ is the number of intersections and $m$ is the number of streets.

Each of the next $m$ lines describes one 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 two endpoints of the street, and $p$ is the probability, in percent, that the Blues Brothers can use this street without being caught. Every street can be traveled in both directions, and there is at most one street between any pair of intersections.

The input ends with a line containing a single zero, which is not part of any test case.

For each test case, compute the probability of the safest path from intersection $1$ (the Palace Hotel) to intersection $n$ (the Honorable Richard J. Daley Plaza in Chicago). There is always at least one path between intersection $1$ and intersection $n$.

Print this probability as a percentage with exactly six digits after the decimal point, followed by a single space and the word percent. Print one line for each test case.