The transport system of the city of Föràg consists of stations and two-way trains connecting the stations, the th of which takes minutes go from station to station or from station to station . Konajya is currently near station after visiting the Föràgian War Museum. However, she wants to go visit the Lastrevia cultural festival which is conveniently going to be held directly beside station in minutes. To use the Föràgian transport system, Konajya must first buy a transport pass. There are levels of passes, the th of which gives access to the first trains in the order given in the input statement. Help Konajya find the minimum level of the transport pass that she must buy to reach the cultural festival before it starts! (You may assume the time needed to get to the station and to buy the pass is negligible)

#### Constraints

In all subtasks,

##### Subtask 1 [15%]

##### Subtask 2 [85%]

No additional constraints.

#### Input Specifications

The first line contains two integers, and .

lines will follow. The th of these will contain the integers , and .

The last line will contain three more integers, , , and .

#### Output Specifications

Output the minimum level of the Föràgian transport pass that Konajya must get so that she can get from station to station in less than minutes. If this is not possible print `-1`

instead.

#### Sample Input

```
4 4
1 4 10
1 2 3
3 4 2
2 3 1
1 4 9
```

#### Sample Output

`4`

## Comments

I was looking at this problem and https://dmoj.ca/problem/ccc15s4 and I realized that they were quite similar. However, after implementing a similar solution I couldn't entirely get the full solution on the other problem. Therefore I think my solution may have had flaws that were not picked up by the test cases. Can anyone check my code and figure out if I have the correct solution or just one that managed to pass all of this problem's test cases?

@max Adding

`if (d > dist[at]) continue;`

right after popping your queue solves the problem. Without it the worst case runs in . Why? Because in Dijkstra's algorithm a vertex can have multiple weights in the queue, so to work around it we only proceed if the node is not "old". (also apparently i don't know how to reply to a comment)so is it equivalent to keeping a visited array?

AC! Thank you.

I am fairly certain that I have implemented the intended solution to this question, however my programme is unable to make it past case #72 of the second batch due to a TLE verdict.

I am using optimised streams for I/O; and have declared all arrays globally as recommended on the tips page.

Additionally, I have tried:

`__attribute__ ((hot))`

before the definition of my main routineAre there any more optimisations I can make in order for my programme to be accepted?