24466번 - 도피

감옥에서 탈출한 병준이는 경찰에 잡히지 않기 위해 도망 다니고 있다. 병준이를 잡기 위해 경찰은 $N$개의 도시에 병력을 파견할 것이다. 이때 병준이가 있을 확률이 높은 도시에 더 많은 병력을 파견할 것이고, 이에 따라 각 도시에 병준이가 있을 확률을 구해야 한다.

경찰은 병준이가 하루 동안 각 도시를 이동할 확률을 알고 있다. 확률에 따라 병준이가 탈옥한 날로부터 $9$일이 지난 후, 병준이가 어느 도시에 있는지 구하려고 한다.

위 그림을 예로 들어 보자. $0$번 도시에 감옥이 있고, 각 도시에서 다른 도시로 이동할 확률이 나타나 있다.

병준이가 탈옥한 지 하루가 지났다면, $1$번 도시에 있을 확률은 $50\%$, $6$번 도시에 있을 확률도 $50\%$이다.

병준이가 탈옥한 지 이틀이 지났다면, $2$번 도시에 있을 확률은 $40\%$, $3$번 도시에 있을 확률은 $50\%$, $4$번 도시에 있을 확률은 $10\%$이다.

병준이의 탈옥 $9$일이 지난 후, 병준이가 있을 확률이 가장 높은 도시와 그 확률을 구하는 프로그램을 작성하시오.

감옥은 항상 $0$번 도시에 존재한다.

첫 번째 줄에 도시의 수 $N$, 이동 가능한 경로의 수 $M$이 주어진다. $(2 \le N \le 100$, $1 \le M \le N^2)$

두 번째 줄부터 $M$줄에 걸쳐 다음과 같이 $3$개의 정수가 입력으로 주어진다.

$u\ v\ w$: $u$ 도시에 있는 병준이는 $v$ 도시로 이동할 확률이 $w\%$이다. $(0 \le u,\ v < N$, $0 \le w \le 100)$

모든 도시에 대하여 다음 도시로 이동할 확률의 합은 $100\%$이다. 이동 전과 이동 후의 도시가 같을 수 있다.

출력의 첫 번째 줄에 병준이가 있을 확률이 가장 높은 도시의 번호를 출력한다. 이러한 도시가 여럿인 경우, 공백으로 구분하여 오름차순으로 출력한다.

출력의 두 번째 줄에 병준이가 해당 도시에 있을 확률을 소수점 아래 $18$자리까지 출력한다. 실수 오차는 허용되지 않는다. 결과가 소수점 아래 $19$자리 이상인 경우, 소수점 아래 $19$자리에서 내림한다.