P043 Dijkstra 最短路径

题目描述

给定一个带权有向图，求从起点 s 到终点 t 的最短路径长度。

输入格式

第一行四个整数 n, m, s, t（1 \le n \le 10^5，0 \le m \le 2 \times 10^5）。
接下来 m 行，每行三个整数 u, v, w，表示从 u 到 v 的有向边，权值为 w。

输出格式

一个整数，最短路径长度；若不可达输出 -1。

样例

输入:
4 5 1 4
1 2 2
1 3 5
2 3 1
2 4 6
3 4 2

输出: 5