德克萨斯淳朴的民众们这个夏天正在遭受巨大的热浪！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生产复函奶油的乳制品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

    Farmer John已经研究过可以把牛奶从威斯康辛运送到德克萨斯州的路线。这些路线包括起点和终点在内一共经过T（1 <= T <= 2500）个城镇，标号为1到T。除了起点和终点外的每个城镇由两条双向道路连向其他城镇。每条道路有一个通过费用（包括油费，过路费等）。

    给定一个地图，包含C（1 <= C <= 6200）条直接连接2个城镇的道路。每条道路由道路的起点Rs、终点Re（1 <= Rs <=T; 1 <= Re <= T）和花费Ci（1 <= Ci <= 1000）组成。求从起始的城镇Ts（1 <= Ts <= T）到终点城镇Te（1 <= Te <= T）最小的总费用。

第1行：4个由空格隔开的整数：T, C, Ts, Te；

第2到C+1行：第i+1行描述第i条路，有3个由空格隔开的整数，Rs, Re和Ci。