在贝尔兰依赖日,决定组织一场盛大的马拉松比赛。 Berland由n个城市组成,其中一些城市通过双向道路相连。每条路都有一定的长度。城市编号为 1 到 n。众所周知,人们可以通过公路从任何一个城市到达任何另一个城市。
n名跑者参加比赛,每个城市一名。但伯兰跑者生性健谈,这就是评审团采取措施避免大批马拉松参赛者聚集的原因。评审团决定,每个跑者都应该从自己的家乡开始马拉松比赛。比赛开始前,每位运动员都会收到一张纸,上面写着该运动员终点线所在城市的名称。每个运动员的终点都是随机选择的,但不能与运动员的起点重合。允许多名运动员在同一个城市完成比赛。所有运动员同时出发,每个人都跑从起点到终点的最短路线。所有运动员都以一种等于 1 的速度奔跑。
比赛结束后,将制定成绩跟踪表,其中运动员将根据跑完距离所用时间的不减少进行排序。排名第一的G级运动员将获得金牌,接下来的S级运动员将获得银牌,其余的运动员将获得铜牌。此外,如果两名或两名以上运动员跑完距离的时间相同,则按照运动员开始跑步的城市编号升序排列。这意味着没有两名运动员共享同一个地方。
根据比赛规则,金牌数g必须满足不等式g1≤g≤g2,其中g1和g2是历史形成的值。类似地,银牌数s必须满足不等式s1≤s≤s2,其中s1和s2也是历史形成的值。
目前,比赛开始前,每位运动员的去向均未知。然而,媒体需要细节,这就是为什么你的任务是计算奖牌的分发方式。如果至少一名运动员在分发过程中获得了不同种类的奖牌,则两种分发奖牌的方式被认为是不同的。
输入
第一输入行包含给定的整数 n 和 m (3 ≤ n ≤ 50, n - 1 ≤ m ≤ 1000),其中 n 是 Berland 城镇的数量,m 是道路的数量。
接下来的 m 行道路描述以三个整数 v、u、c 的组形式给出,它们是相连城镇的数量及其长度(1 ≤ v,u ≤ n,v ≠ u,1 ≤ c ≤ 1000)。每对城市之间只有一条道路。
最后一行包含整数 g1, g2, s1, s2 (1 ≤ g1 ≤ g2, 1 ≤ s1 ≤ s2, g2 + s2 < n)。输入数据编号位于一行,以空格分隔。
输出
打印单个数字——奖牌分发方式的数量。确保该数字符合标准 64 位有符号数据类型。
示例
输入 #1
3 2 1 2 1 2 3 1 1 1 1 1
输出 #1
3
输入 #2
4 5 1 2 2 2 3 1 3 4 2 4 1 2 1 3 3 1 2 1 1
输出 #2
19
输入 #3
3 3 1 2 2 2 3 1 3 1 2 1 1 1 1
输出 #3
4