他去上課的路上要搭捷運
發布時間: July 12, 2018, 1:23 p.m. 最後更新時間: Sept. 15, 2023, 1:01 p.m. 時間限制: 2000ms 記憶體限制: 128M
旲刓，一個充滿了魔法的國度，人人都擁有強大的魔術迴路，尤其是某些電神，隨手寫下的code(簡稱-咒碼)都擁有供應北旲刓三個月電量的電神力，電爆一大群人。
身為在魔法路上打滾的少年Sia喵，當然也不遑多讓的學起了戰鬥用的咒碼靈賦，在經過幾次大大小小的擬似戰役之後(甚至還一路打到了旲北)，和齜牙的入營考的壓線表現，Sia終於要去旲亣進修了!
然而，進修的路必然是充滿阻撓的，除了每周三百魔力的傳送陣票卷，還有在傳送陣上的作業(殺怪)時間，他去上課的路上要搭捷運! (但他還是沒有和同學一樣，拿到優良結業，變成電神...不過，這都是後話了。
傳送陣總是把Sia丟到小橋尾站，而Sia進修要去的旲亣則在科技小樓站，這橫貫了亣旲北地區的漫長行程，總是困擾著這位搭著捷運的少年。
「到底要在大安、忠孝復興還是南京復興轉車啊啊啊啊!!!」
我們知道，在這魔法(?)發達的年代，捷運可視為不用等，另外，轉車也不用花時間。
現在，Sia蒐集了兩站間搭捷運要花的時間，作為Sia的電神朋友，你可以幫他算算看，他最少要花多少時間才能到達目的地嗎?
範例測資就是旲北捷運地圖喵www
第一行有四個正整數N,E,S,G，N代表站數，E代表有多少條捷運線讓兩站相連，S為Sia出發的起點，G為目標。
接下來有E行，每行有a,b,v三個正整數，代表捷運線的資料，其中捷運會從站a出發，到站b，其中會花費v的時間，注意，就這條捷運線而言，b並不能到a，也就是這是一條單向的捷運線。
在20%的測資中 1<N<=20,1<=E<380
在60%的測資中 1<N<=1000,1<=E<999000
在100%的測資中 1<N<1000000,1<=E<N(N-1),1<=S<G<=N,1<=a、b<=N,1<=v<=10000
(此百分比數為向上包含)
請輸出Sia最少要花多少時間才能到達上課地點?
若無法到達，請輸出-1。
20 44 1 20 1 2 5 2 3 5 3 4 5 4 5 5 5 6 5 6 7 5 7 6 5 6 5 5 5 4 5 4 3 5 3 2 5 2 1 5 2 14 5 14 12 5 12 11 5 11 8 5 8 7 5 7 17 5 17 18 5 18 17 5 17 7 5 7 8 5 8 11 5 11 12 5 12 14 5 14 2 5 15 5 5 5 12 5 12 13 5 13 10 5 10 9 5 9 8 5 8 9 5 9 10 5 10 13 5 13 12 5 12 5 5 5 15 5 15 16 5 16 18 5 18 20 5 20 18 5 18 16 5 16 15 5
40
