TopCoder

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

80.0% (4/5)

Tags

Description

INFOR樂園開幕了!!
最令人期待的遊樂設施就是多重溜滑梯,什麼?你不知道什麼是多重溜滑梯?沒關係我也不知道
簡單來說就是有很多的點,你有可能是從一個更高的地方滑下來到這個點,也可以再從這個點往下滑
為了維護樂園的客人素質,請勿做出往溜滑梯上爬的舉動
你開開心心跟你的女朋友跑到多重溜滑梯裡面玩,沒想到玩一玩你們居然走散了
傷著腦筋的你只好放棄遊樂的快樂心情,開始尋找你的女友
沒想到這時候你聽到了你女友的慘叫聲,原來是溜下去的時候受傷了
身為一個可悲的男朋友,你不想及時趕到他身邊,但又不能違反了遊樂場規則
你該如何以最久的時間抵達你女朋友的位置呢?

Input Format

第一行有兩個整數$1 \le N \le M \le 5 \times 10^ 6$
接下來的$M$行,每一行有三個正整數$s_i, e_i c_i ( 1 \leq s_i, e_i \leq N, 1 \leq c_i \leq 10^ {9} )$代表從$s_i$有一條花費時間為$c_i$的溜滑梯連到$e_i$
最後的一行有兩個正整數$st, ed$代表你在的位置與你女朋友所在的位置

Output Format

請輸出你最久一定要多晚才能看到女友
若是無法到達,請輸出-1

Sample Input

8 9
6 5 80
6 4 8
5 8 17
6 2 93
4 1 8
8 7 97
8 3 34
5 7 93
5 4 68
6 3

Sample Output

131

Hints

子任務(測資)額外限制分數
1(0~9)$1 \le N, M \le 3 \times 10 ^ 3 $30
3(10~19)$1 \le N, M \le 3 \times 10^ 5 $ 30
3(20~29)無額外限制40

就是這樣你才沒女友,哼

Problem Source

Problem Set By oToToT
Description By Pooh

Subtasks

For Testdata: 0 ~ 9, Score: 30
For Testdata: 10 ~ 19, Score: 30
For Testdata: 20 ~ 29, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 262144 65536
1 2000 262144 65536
2 2000 262144 65536
3 2000 262144 65536
4 2000 262144 65536
5 2000 262144 65536
6 2000 262144 65536
7 2000 262144 65536
8 2000 262144 65536
9 2000 262144 65536
10 2000 262144 65536
11 2000 262144 65536
12 2000 262144 65536
13 2000 262144 65536
14 2000 262144 65536
15 2000 262144 65536
16 2000 262144 65536
17 2000 262144 65536
18 2000 262144 65536
19 2000 262144 65536
20 2000 262144 65536
21 2000 262144 65536
22 2000 262144 65536
23 2000 262144 65536
24 2000 262144 65536
25 2000 262144 65536
26 2000 262144 65536
27 2000 262144 65536
28 2000 262144 65536
29 2000 262144 65536