시카고까지 106마일

영화 블루스 브라더스에서, 엘우드와 제이크가 자란 고아원은 두 사람이 시카고 쿡 카운티 감정평가원에 밀린 세금 $5000을 내지 못하면 교육위원회에 팔리게 됩니다. 팰리스 호텔 무도회장에서 공연해 이 돈을 번 뒤, 두 사람은 시카고로 가는 길을 찾아야 합니다.

하지만 이는 말처럼 쉽지 않습니다. 경찰과 컨트리 밴드, 그리고 나치 무리가 이들을 뒤쫓고 있기 때문입니다. 게다가 시카고까지는 106마일이나 남았고, 날은 어두우며, 두 사람은 선글라스를 끼고 있습니다.

이들은 신의 임무를 수행 중이므로, 시카고로 가는 가장 안전한 경로를 찾도록 도와주세요. 여기서 가장 안전한 경로란 붙잡히지 않을 확률이 최대가 되는 경로를 뜻합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스는 두 정수 $n$과 $m$으로 시작합니다 ($2 \le n \le 100$, $1 \le m \le n(n-1)/2$). $n$은 교차로의 수, $m$은 고려할 거리의 수입니다.

이어지는 $m$개의 줄에는 각 거리의 정보가 주어집니다. 각 줄에는 세 정수 $a$, $b$, $p$가 있습니다 ($1 \le a, b \le n$, $a \ne b$, $1 \le p \le 100$). $a$와 $b$는 거리의 두 끝점이고, $p$는 블루스 브라더스가 붙잡히지 않고 이 거리를 지날 확률(퍼센트 단위)입니다. 모든 거리는 양방향으로 지날 수 있으며, 두 교차로 사이에는 거리가 최대 한 개만 존재합니다.

입력의 끝에는 $0$ 하나만 있는 줄이 주어지며, 이 줄은 어떤 테스트 케이스에도 포함되지 않습니다.

각 테스트 케이스마다, 교차로 $1$(팰리스 호텔)에서 교차로 $n$(호노러블 리처드 J. 데일리 광장)까지 가는 가장 안전한 경로의 확률을 구하세요. 교차로 $1$과 $n$ 사이에는 항상 적어도 하나의 경로가 존재합니다.

이 확률을 소수점 아래 정확히 여섯 자리까지의 퍼센트 값으로 출력하고, 그 뒤에 공백 하나와 단어 percent를 붙이세요. 테스트 케이스마다 한 줄씩 출력합니다.