찰스의 전기차

찰스는 매일 집에서 직장으로 갔다가 다시 집으로 돌아온다. 이동에는 도시와 도시를 잇는 고속도로만 쓴다. 찰스는 환경을 생각해서 전기차를 사기로 했다. 그런데 이 나라에는 아직 전기차가 흔하지 않다. 충전은 도시 안에서만 되고, 도시 사이의 고속도로에는 충전소가 하나도 없다. 게다가 전기차는 배터리 용량 말고는 전부 같은 차다. 배터리가 비싸기 때문에 찰스는 되도록 작은 배터리를 단 차를 사고 싶다.

배터리가 작으면 퇴근길이 훨씬 길어지고, 아내 샬럿은 이를 못마땅해한다. 오래 다툰 끝에 두 사람은 이렇게 합의했다. 일반 자동차로 직장에서 집까지 갈 때의 최단 경로 길이를 기준으로 삼아, 찰스가 고른 경로의 길이가 그보다 $X$% 넘게 길어지지만 않으면 샬럿도 받아들인다. 찰스는 이 조건을 지키면서, 도시를 거치지 않고 고속도로 위를 한 번에 달려야 하는 거리의 최댓값이 가장 작아지는 경로를 찾으려 한다.

충전에 걸리는 시간은 무시한다.

첫째 줄에 도시의 수 $N$, 고속도로의 수 $M$, 위에서 말한 비율 $X$가 주어진다 ($2 \le N \le 10\,000$, $1 \le M \le 100\,000$, $0 \le X \le 10\,000$). 찰스는 $1$번 도시에 살고 $N$번 도시에서 일한다.

다음 $M$개 줄에는 각각 세 정수 $C_1$, $C_2$, $T$가 주어진다 ($1 \le C_1 \le N$, $1 \le C_2 \le N$, $1 \le T \le 10^9$). 도시 $C_1$과 도시 $C_2$를 잇는 길이 $T$의 고속도로가 있다는 뜻이다. 이 고속도로는 양방향으로 달릴 수 있고, 중간에 다른 도시를 지나지 않는다. $1$번 도시에서 $N$번 도시로 가는 경로는 항상 존재한다.

$1$번 도시에서 $N$번 도시로 가는 경로 가운데, 길이 $L$이 최단 경로 길이 $D$에 대해 $100L \le (100 + X)D$를 만족하는 경로만 고려한다. 그런 경로에서 도시를 거치지 않고 고속도로 위를 한 번에 달리는 거리의 최댓값을 가장 작게 만들었을 때, 그 값을 정수 하나로 출력한다.