URI Online Judge | 2784


By OBI BR Brasil

Timelimit: 1

The residents of the Western Brazilian Islands (IBO) are assiduous players of the latest online game, Wizards and Warriors. So competitive have become the Wizards and Warriors at the IBO that the game developer decided to install on one of the islands a server dedicated only to IBO players.

However, the company knows that if players think the new server is unfair, they will stop playing Wizards and Warriors, generating countless losses. To evaluate whether the new server is fair, players will compare the performance of the game on the island that has the fastest connection and the performance on the island that has the slowest connection to the new server. If the difference in performance is too great, the residents of the furthest island will feel wronged and will leave the game.

The IBO internet connection works via a fiber optic cable system. Pairs of islands are connected by cables, and each cable takes a certain time (called ping) to communicate information between the two parts. When two islands communicate through a series of cables (hence through intermediate islands), the ping between them is the sum of the pings of each cable in the path. The IBO network was implemented by great programmers and therefore a pair of islands always communicates through the path with the least possible ping.

Given the configuration of the IBO network and the island where the company wants to install the new server, determine the difference between the pings of the island with the lowest and highest pings to the server.


The first line contains N (2 ≤ N ≤ 1000) and M (N - 1 ≤ M ≤ 105), the number of islands and the number of fiber optic cables, respectively. The islands are numbered from 1 to N. Each of the following M lines contains three integers Ui (1 ≤ Ui ≤ N), Vi (1 ≤ Vi ≤ N) and Pi (1 ≤ Pi ≤ 1000) and describes a cable between Ii and Vi islands with Pi-ping (note that cables transmit information in both directions). Finally, the last line contains an integer S (1 ≤ S ≤ N), the island number on which the server will be installed.

Each pair of islands is connected by at most one fiber optic cable, and no cable connects an island to itself. It is guaranteed that any island can communicate with any other via some fiber optic cable path.


Your program should produce an integer representing the difference between the ping of the island with the highest ping to the server, and the one of the island with the lowest ping to the server. Note that the island on which the server is located is not considered in the lowest ping calculation.

Input Samples Output Samples

4 5

2 1 5

1 3 4

2 3 6

4 2 8

3 4 12



6 11

1 2 3

6 1 9

2 6 10

2 3 8

5 3 3

4 3 2

2 4 12

6 4 1

4 5 9

1 5 16

5 6 5