题目描述

给定一个含N个点，M条带权有向边的图，每条边的权值均为正整数。求点S到点T的最短路。如果S→T的路径不存在，输出-1。

输入格式

第一行是两个正整数N，M；
之后M行，每行三个正整数u，v，w，表示一条u→v的有向边，该边的权值为w。输入数据保证无重边（u→v的边出现多次）和自环（u→u的边）。
之后一行是两个正整数S，T，表示起点和终点。

输出格式

一个整数。如果S→T的路径存在，输出S→T最短路的长度；否则，输出-1。

样例

输入

6 10
1 2 6
1 3 10
2 3 3
4 2 2
4 5 2
3 4 4
3 6 13
4 6 7
5 6 4
2 5 10
1 6

输出

19

数据规模及约定

50%的数据：N≤1000，M≤10000
100%的数据：N≤20000，M≤200000
输入的所有数，以及答案都在int范围内