Problem E
Charles in Charge

Picture by Frank Hebbert via Flickr

Every day, Charles drives from his home to work and back. He uses the highways of the country that run from one city to another. Charles has decided that he wants to help the environment by buying an electrical car. Electrical cars, however, are not very common in his country yet. They can only be charged inside a city; there are no charging stations along the highways in between the cities. Moreover, all electrical cars are identical except for one thing: the size of the battery. As batteries are very expensive, Charles would like to buy a car with battery that is as small as possible.

However, this greatly increases the time it takes for him to get home, much to the distaste of his wife, Charlotte. This has spawned an argument, and after much discussion they have decided to compromise: Charlotte is fine with Charles taking a longer route, as long as it its length is at most $X \% $ longer than the length of shortest route that Charles could have taken to get home from work by using a regular car. Charles has agreed with this, and he now wants to find a route that minimizes the size of the car battery that he needs, i.e. the route that minimizes the maximum distance that Charles has to drive on a highway without passing through a city.

The amount of time Charles spends to charge his car can be neglected.

Figure 1: The graph of the second and third test case. The shortest path has length $16$. In the second testcase, Charles’s travel distance may not exceed $16 \cdot 1.15 = 18.4$ distance units. As a result, he cannot use a battery with which he can travel $4$ distance units, as the red path $1$–$4$–$5$–$6$–$8$–$9$ has length $20$. Therefore, he uses the blue path $1$–$4$–$7$–$8$–$9$, which has length $18$, and the longest edge has length $5$. In the third test case, he is allowed to travel $16 \cdot 1.30 = 20.8$ distance units, so he can follow the red path, where the longest edge has length $4$.

Input

The input starts with integers $2 \leq N \leq 10\, 000$, $1 \leq M \leq 100\, 000$ and $0 \leq X \leq 10\, 000$: the number of cities, the number of highways connecting the cities and the aforementioned percentage $X$. City $1$ is the place where Charles lives and city $N$ is where he works.

Then follow $M$ lines with on each line three integers: $1 \leq C_1 \leq N$, $1 \leq C_2 \leq N$, $1 \leq T \leq 10^9$. This means that there is a highway of length $T$ connecting cities $C_1$ and $C_2$ (Charles can traverse the highway in both directions) without passing through any other cities. You may assume that there exists a path from city $1$ to city $N$.

Output

The output is a single integer: the smallest maximum distance that Charles has to travel on a highway without passing through a city, such that the route he takes is at most $X\% $ longer than the shortest route.

2 1 100
1 2 5

5

9 8 15
1 9 16
1 4 4
4 5 4
5 6 4
6 8 4
4 7 5
7 8 5
8 9 4

5

9 8 30
1 9 16
1 4 4
4 5 4
5 6 4
6 8 4
4 7 5
7 8 5
8 9 4

4