Fun in Föràg

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Java 4.0s
Memory limit: 64M

Problem type

The transport system of the city of Föràg consists of N stations and M two-way trains connecting the stations, the ith of which takes c_i minutes go from station a_i to station b_i or from station b_i to station a_i. Konajya is currently near station A 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 B in C minutes. To use the Föràgian transport system, Konajya must first buy a transport pass. There are M levels of passes, the ith of which gives access to the first i 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)


In all subtasks,
1\le N\le100\space000
1\le M\le200\space000
1\le a_i,b_i,A,B\le N
1\le c_i\le10^6
1\le C\le 10^{11}

Subtask 1 [15%]

1 \le N, M \le 2 \space 000

Subtask 2 [85%]

No additional constraints.

Input Specifications

The first line contains two integers, N and M.
M lines will follow. The ith of these will contain the integers a_i, b_i and c_i.
The last line will contain three more integers, A, B, and C.

Output Specifications

Output the minimum level of the Föràgian transport pass that Konajya must get so that she can get from station A to station B in less than C 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



There are no comments at the moment.