Melanie, a student at Phillips Exeter Academy has discovered a new theorem regarding relative velocities, which she calls the *Chain Rule*. Now she must drive to Washington, D.C. to show her groundbreaking results to the president.

The world she lives in is made up of cities, numbered and highways. Phillips Exeter Academy, where Melanie starts, is located in city and Washington, D.C. is city . The highway connects cities and , takes minutes to travel on, and can be taken in either direction.

However, Melanie must first visit her rival, Alex Song, to brag about her results. Unfortunately, Melanie has no idea which city Alex actually lives in. Regardless of which city Alex lives in, Melanie wants to travel from Phillips Exeter to Alex's house then to Washington, D.C. in the minimum amount of time possible. Knowing that Alex's house may be extremely inconveniently located, Melanie wants to determine how long of a trip she may need in the worst case. You must consider all possible locations of Alex's house, then determine the longest time that Melanie may need to complete her trip, given that she always takes the fastest route from Phillips Exeter to Alex's house then to Washington, D.C.

Note that Alex may also live in city or , in which case Melanie does not need to go out of her way. Also note that Melanie is allowed to pass through Washington, D.C. on her way to Alex's house, however she must still make the journey from Alex's house back to Washington. There will always exist a path between any two cities.

#### Hint

Learn Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

#### Input Specification

The first line of input contains two space-separated integers, and . The next lines contain three space separated integers, , , and .

#### Output Specification

Print a single integer, the maximum amount of time that Melanie may need to travel from Exeter to Alex's house to Washington, D.C., given that she always takes the optimal route.

#### Sample Input

```
5 5
0 1 5
1 2 4
0 3 8
2 3 2
4 2 3
```

#### Sample Output

`13`

#### Explanation

If Alex lives in city , the shortest path from to would take minutes, and the shortest path from to would take minutes. Thus the trip will take minutes. If Alex lived anywhere else, the shortest trip would take minutes. Therefore, the longest trip Melanie may be required to take will take minutes.

## Comments

Can someone please give me a hint on what I'm doing wrong? Do I just need to optimize or is my whole idea wrong?

Your Dijkstra's runs in , which TLEs. There's another variant of Dijkstra's which runs in

Using a priority queue right?

you can do it with a normal queue as well, just don't use an adjacency matrix ;)

In python I feel like I have created the fastest algorithm I can think of. However I am failing with TLE on the last two test cases. Could I have a hint on how to proceed?

EDIT:I had too do two things to AC. One was a way of optimising my dijkstra's by a constant factor. The other was removing my comments, the latter presumably worked because python is an interpreted language.

Will all cities be, directly or indirectly, connected?

"There will always exist a path between any two cities."

Where did the submissions go?

are you perhaps trying to view this problem while in a contest?

Time limit is changed to 5s; all solutions rejudged.

Will there be more than one highway between two identical cities?

No.

So you're saying that Melanie needs to "exeter" home to travel to Washington?

Please stop making me laugh, I'm trying to do the question