作問訓練２ / The second of practicing to make problem

タイトルにあってるか間違ってるかもわからない英語が入りましたが、今日は日本語で問題考えた後、英文バージョンもつくってみようとかおもったり・・・

単純アルゴリズム問題

***交通渋滞 / Traffic Jam

問題

TKC王国は車社会である。
そのため交通渋滞などは日常茶飯事となっている。
TKC王国の住民であるカイトは寝坊をよくするため、会社に遅刻しないためにもなるべく最短のルートで通勤したい。
そこでカイトは友達であるあなたに会社への最短ルートを計算するプログラムを作成を依頼してきた。

入力

入力の一行目は街の数N(2<=N<=10^5)、道の数M(1<=M<=2*10^5)、カイトの家がある街X(1<=X<=N)、会社がある街Y(1<=Y<=N)が空白区切りで与えられる。
続くM行には道路の情報が与えられる。道路の情報にはつなぐ街A,B（1<=A,B<=N),かかる時間C(1<=C<=10^8)が空白くぎりで含まれる。

出力

カイトの家から会社まで最短の時間を一行に出力せよ。

Statement

TKC Kingdom's people always use cars to move.
So there are many traffic jams everyday.
Kite who lives TKC Kingdom usually oversleep, but he wants to commute the company in as early route as he can because he want to get on time.
Then he asked you who is his friend to make program to calculate for route which is earliest.

Input

First line contains the number of town N(2<=N<=10^5), the number of road M(1<=M<=2*10^5), the town X which there is Kite's home(1<=X<=N), and the town Y which there is the company(1<=Y<=N), separated spaces.
Next M lines contain information of road. Each information contains the town A and B which consist of road(1<=A,B<=N), and the time C to cross the road(1<=C<=10^8), separated spaces.