URI Online Judge | 3144

G of Graph

By Roger Eliodoro Condras, UFSC-ARA BR Brazil

Timelimit: 1

This problem was originally written for the first open contest I created here at URI last year, but due to an error with the test case files it cannot be included in the test in time. So it is only fair that now he is part of the warm-up for my second race. Below is the original text of the problem! :)

Last week Tobias, Gabriel and Me were choosing the questions to compose the test, and then Gabriel declared "G de Grafo huh!" and I will not deny that the idea was great. After that I had the brilliant idea of ​​asking all the questions of the author's proof, and I regretted it a little. If resolving the issues is already difficult, generating test cases and creating validation codes can be even worse.

I confess that I tried, but no idea seemed good to mix graphs with the strike, but as it is customary for questions in the marathon to have a long text that says nothing with nothing to introduce the problem, let's imagine some story.

Let's say ... At the UFSC Campus here in Araranguá there are rooms. And between the rooms there are corridors. These corridors form paths that connect rooms with a certain length, and there may be more than one path that leaves one room to another. So far, no surprise, I am calling UFSC Campus Araranguá a graph, the apex rooms and the edge corridors. If the reader was attentive, he also noticed that the graph can have cycles and the edges are weighted. So far no surprise.

Let's also say ... Well, I don't know. For some random reason or some conspiratorial force in the universe someone. It could be Tobias, or Gabriel, or both. This ... The two want to go through all the rooms of the Campus, starting and ending the route in the same room, without creating any cycle on the route and covering the shortest possible distance during the entire path. It is possible to go through the same room or corridor more than once if necessary. Why they want to do this is a mystery even to me, I have no creativity to come up with a good excuse.

So, given the information in the graph, can you tell me which is the minimum path they need to take according to the restrictions described above? I hope so, otherwise your team will not win balloon on this issue. ;)


The first line of the entry contains two integers N (2 \(\leq\) N \(\leq\) 500) and M (1 \(\leq\) M \(\leq\) 124750) that represent the number of rooms and the number of corridors on the UFSC-Araranguá campus respectively. In the second line, an integer O (1 \(\leq\) O \(\leq\) N) indicating the room they will start and end the journey. Each of the next M lines is composed of three integers U, V (1 \(\leq\) U, V \(\leq\) N e U \(\neq\) V) and D (1 \(\leq\) D \(\leq\) 500) that indicate that there is a D-length corridor that connects rooms U and V. It is always possible to use the corridor in both directions and it is guaranteed that there are no repeated edges at the entrance.


A single integer in a row. The minimum distance for Tobias and Gabriel to go through all the rooms without doing any cycle during the way, leaving and returning to the same room of origin.

Input Samples Output Samples

5 6
1 2 15
1 3 10
2 3 1
2 4 5
4 5 20
3 4 3


4 5
1 2 2
1 3 1
1 4 5
2 3 20
4 2 3