题目描述

小P和小R在玩一款益智游戏。游戏在一个正权有向图上进行。 小P控制的角色要从$A$点走最短路到$B$点，小R控制的角色要从$C$点走最短路到$D$点。 一个玩家每回合可以有两种选择，移动到一个相邻节点或者休息一回合。 假如在某一时刻，小P和小R在相同的节点上，那么可以得到一次特殊奖励，但是在每个节点上最多只能得到一次。 求小P和小R最多能获得多少次特殊奖励。

输入

第一行两个整数$n$，$m$表示有向图的点数和边数。 接下来$m$行每行三个整数$x_i，y_i，l_i$，表示从$x_i$到$y_i$有一条权为$l_i$的边。 最后一行四个整数$A，B，C，D$，描述小P的起终点，小R的起终点。

输出

一个整数表示小P和小R最多能获得多少次特殊奖励。若小P不能到达$B$点或者小R不能到达$D$点则输出$-1$。

输入样例

5 5
1 2 1
2 3 2
3 4 4
5 2 3
5 3 5
1 3 5 4

输出样例

2

提示

【数据规模及约定】 对于30%的数据，满足$n≤50$； 对于60%的数据，满足$n≤1000，m≤5000$； 对于100%的数据，满足$n≤50000，m≤200000，1≤l_i≤5×10^8$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。