德克薩斯純樸的民眾們這個(gè)夏天正在遭受巨大的熱浪?。。∷麄兊牡驴怂_斯長角牛吃起來不錯(cuò)，可是他們并不是很擅長生產(chǎn)富含奶油的乳制品。Farmer John此時(shí)以先天下之憂而憂，后天下之樂而樂的精神，身先士卒地承擔(dān)起向德克薩斯運(yùn)送大量的營養(yǎng)冰涼的牛奶的重任，以減輕德克薩斯人忍受酷暑的痛苦。

FJ已經(jīng)研究過可以把牛奶從威斯康星運(yùn)送到德克薩斯州的路線。這些路線包括起始點(diǎn)和終點(diǎn)先一共經(jīng)過T (1 < = T < = 2,500)個(gè)城鎮(zhèn)，方便地標(biāo)號(hào)為1到T。除了起點(diǎn)和終點(diǎn)外地每個(gè)城鎮(zhèn)由兩條雙向道路連向至少兩個(gè)其它地城鎮(zhèn)。每條道路有一個(gè)通過費(fèi)用（包括油費(fèi)，過路費(fèi)等等）?？紤]這個(gè)有7個(gè)城鎮(zhèn)的地圖。城鎮(zhèn)5是奶源，城鎮(zhèn)4是終點(diǎn)（括號(hào)內(nèi)的數(shù)字是道路的通過費(fèi)用）。

經(jīng)過路線5-6-3-4總共需要花費(fèi)3 (5-> 6) + 4 (6-> 3) + 3 (3-> 4) = 10的費(fèi)用。

給定一個(gè)地圖，包含C (1 < = C < = 6,200)條直接連接2個(gè)城鎮(zhèn)的道路。每條道路由道路的起點(diǎn)Rs，終點(diǎn)Re (1 < = Rs < = T; 1 < = Re < = T)，和花費(fèi)(1 < = Ci < = 1,000)組成。求從起始的城鎮(zhèn)Ts (1 < = Ts < = T)到終點(diǎn)的城鎮(zhèn)Te(1 < = Te < = T)最小的總費(fèi)用。

第一行：4個(gè)由空格隔開的整數(shù)：T, C, Ts, Te。

第2到第C+1行：第i+1行描述第i條道路。有3個(gè)由空格隔開的整數(shù)：Rs, Re和Ci。

第一行：一個(gè)單獨(dú)的整數(shù)表示Ts到Te的最短路的長度。

數(shù)據(jù)保證至少存在一條道路。

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

7