德克薩斯純樸的民眾們這個(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)號為1到T。除了起點(diǎn)和終點(diǎn)外的每個(gè)城鎮(zhèn)由兩條雙向道路連向至少兩個(gè)其它的城鎮(zhèn)。每條道路有一個(gè)通過費(fèi)用（包括油費(fèi)，過路費(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的最小總費(fèi)用。數(shù)據(jù)保證至少存在一條道路。

【樣例說明】
5->6->1->4 (3 + 1 + 3)

編程練習(xí) 基礎(chǔ)