U33239.BF-模板-太空基地
普及/提高-
通过率：0%
时间限制：1.00s
内存限制：128MB
题目描述
题目描述
公元2070年，人类在火星上建造的数个太空基地，太空基地的编号为 1 至 n，太空基地之间共有 m 条单向联通的道路，走每条路都会消耗小码君太空服中的氧气，幸运的是，太空基地之间有免费的泊船，不仅不消耗氧气，还可以回复氧气。问从 s 基地移动到 t 基地最少消耗多少氧气。
输入格式
第一行四个由空格隔开的整数，分别表示 n，m，s，t;
之后的m行，每行三个正整数 x，y，z，表示一条从 x 到 y 长度为 z 的单向边，若 z>0 表示消耗氧气，若 z<0 表示可以搭船并恢复 −z 氧气。
输出格式
一个整数表示最少消耗的氧气，如果无法到终点，输出 1000000000
输入输出样例
输入#1
5 5 1 5 1 2 5 1 3 7 3 5 1 1 4 10 4 5 -4
输出#1
6
说明/提示
1≤n,m≤1000
每条路径的距离不超过 1e9