题目描述

给定一个含n个点，m条边的带权有向图，点的编号为1 ~ n，边权均为正整数。用搜索的方法求点s到点t的最短路。

输入格式

第一行是两个正整数：n，m。
之后有m行，每行三个正整数v1，v2，w，表示边v1→v2的权值为w。对于任意两点v1和v2，v1→v2在数据中至多只出现一次，但v1→v2和v2→v1可能共存，且权值未必相同。
最后一行是两个正整数：s，t。

输出格式

如果s→t的路径存在，则输出最短路径长。若不存在则输出-1。

样例

输入

6 8
1 2 5
1 3 6
3 2 2
2 4 9
4 3 3
4 5 8
5 6 3
4 6 4
1 6

输出

18