Problem
国の道路網の説明が表示されます。あなたのタスク –都市 A と都市 B の間の最短経路の長さを見つけてください。
入力
道路網は、入力ファイルで次のように指定されます。最初の行には、数値 N と K (1<=N<=100000、0<=K<=300000) が含まれます。道路の数。次の K 行のそれぞれには、双方向道路の説明が含まれています – 3 つの整数 ai、bi、li (1aibiN、1li106)。これは、ai 市から bi 市に至る長さ li の道路があることを意味します。最後の行には、2 つの数値 A と B – が含まれています。最短距離を計算する必要がある都市の数 (1<=A,B<=N )
インプリント
単一の数値を出力する必要があります –必要な都市間の距離。 都市 A から都市 B まで車で行くことができない場合は、–1 を出力してください。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |