图上最短路III

题目描述

给定一张 $n$ 点 $m$ 条边构成的带权有向图，并且给定起点 $S$ 以及终点 $T$，请求出 $S$ 到 $T$ 的最短路径的长度，如果 $S$ 和 $T$ 之间不可达，则输出unreachable。

输入格式

第一行为四个整数 $n,m,S,T$，分别表示点数，边数，起点和终点。 接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示节点 $u$ 和节点 $v$ 之间存在一条从 $u \rightarrow v$ 且长度为 $w$ 的边。

数据保证给定的图中不存在负权回路。

数据范围: $1 \le n \le 500$ $1 \le m \le 20000$ $1 \le S, T, u, v \le n$ $-10^9 \le w \le 10^9$

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

6 9 1 6
1 2 1
1 3 2
2 4 -3
3 5 3
3 4 1
5 6 1
4 6 3
3 2 2
5 4 1

样例输出 #1

1

提示

一条可能的最短路。