//注：本題為 a210 的變種，可以先寫完那題再過來。
在科技發達的未來，人類掌握了「超空間航道」技術，擺脫了光速的限制，進入了繁榮的星際時代。
戴克斯特拉(Dijkstra)是在泰拉公司上班的一名員工，他每天的工作就是將公司一份貴重的貨物送達目的地。
今天是個特別的日子：【大小姐想讓人告白】劇場版在今天要撥出了。為了不錯過時間，戴克斯特拉希望能在最短的時間內將今天的貨物送到站。
戴克斯特拉有一個特殊的裝置，能讓他瞬間穿越超空間航道，而不耗費任何時間。但是他出門前忘記充電了，在用了一次之後裝置就會因為沒電而無法使用。
你能幫戴克斯特拉算算他送到貨最少需要多少時間嗎？
注意：由於空間扭曲等等複雜的因素，兩顆星星之間可能沒有架設航道，
也有可能直接搭乘從A星到C星的航班所花費的時間，不一定比先從A星搭到B星，再從B星搭到C星所花的時間短。
輸入第一行為四個整數 N、M、S、E ，代表這片星域有編號 0~N-1 的共 N 顆星星，總共有 M 個連接兩顆不同星星的超空間航道，並且戴克斯特拉將把貨物從 S 星送到 E 星。
接下來的 M 行，每一行都有三個數字 X、Y、T ，代表X星與Y星之間有超空間航道，而從X星抵達Y星(或從Y星抵達X星)所花的時間為 T 。
兩顆星星間最多只有一個超空間航道。
戴克斯特拉的裝置，能讓他瞬間穿越一個超空間航道，但在用了一次後就會因為沒電而無法使用。
2 ≤ N，M ≤ 3×105。
0 ≤ S，E ≤ N-1 且 S ≠ E。
0 ≤ X，Y ≤ N-1 且 X ≠ Y。
1 ≤ T ≤ 105。
輸出單個整數，代表從 S 星到 E 星所需花費的最短時間。
如果不能從從 S 星抵達 E 星，輸出-1。
5 5 0 4 0 1 3 1 2 4 2 4 11 2 3 1 3 4 6
7
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (20%): 1.0s , <1M
不公開 測資點#4 (20%): 1.0s , <1M
不公開 測資點#5 (20%): 1.0s , <1M
範例測資中，花費最短時間的路徑為0 → 1 → 2 → 4 ，並用裝置瞬間穿越 2 → 4 的航道。
最後時間為3 + 4 + 0 = 7。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 25 | a212 | 119 | 2023-04-02 11:45 |