CF38H.The Great Marathon

On the Berland Dependence Day it was decided to organize a great marathon. Berland consists of n cities, some of which are linked by two-way roads. Each road has a certain length. The cities are numbered from 1 to n. It is known that one can get from any city to any other one by the roads.

n runners take part in the competition, one from each city. But Berland runners are talkative by nature and that's why the juries took measures to avoid large crowds of marathon participants. The jury decided that every runner should start the marathon from their hometown. Before the start every sportsman will get a piece of paper containing the name of the city where the sportsman's finishing line is. The finish is chosen randomly for every sportsman but it can't coincide with the sportsman's starting point. Several sportsmen are allowed to finish in one and the same city. All the sportsmen start simultaneously and everyone runs the shortest route from the starting point to the finishing one. All the sportsmen run at one speed which equals to 1.

After the competition a follow-up table of the results will be composed where the sportsmen will be sorted according to the nondecrease of time they spent to cover the distance. The first g sportsmen in the table will get golden medals, the next s sportsmen will get silver medals and the rest will get bronze medals. Besides, if two or more sportsmen spend the same amount of time to cover the distance, they are sorted according to the number of the city where a sportsman started to run in the ascending order. That means no two sportsmen share one and the same place.

According to the rules of the competition the number of gold medals g must satisfy the inequation _g_1 ≤ g ≤ _g_2, where _g_1 and _g_2 are values formed historically. In a similar way, the number of silver medals s must satisfy the inequation _s_1 ≤ s ≤ _s_2, where _s_1 and _s_2 are also values formed historically.

At present, before the start of the competition, the destination points of every sportsman are unknown. However, the press demands details and that's why you are given the task of counting the number of the ways to distribute the medals. Two ways to distribute the medals are considered different if at least one sportsman could have received during those distributions different kinds of medals.

在贝尔兰德依赖日，决定举办一场盛大的马拉松比赛。贝尔兰德由 $n$ 座城市组成，其中某些城市之间由双向道路连接。每条道路具有确定的长度。城市编号为 $1$ 至 $n$。已知任意两座城市之间均可通过道路相互到达。

共有 $n$ 名运动员参赛，每座城市各派出一名。但贝尔兰德的运动员天性健谈，因此裁判组采取措施避免马拉松参与者大规模聚集。裁判组决定：每位运动员必须从自己家乡所在的城市出发。起跑前，每位运动员将获得一张纸条，上面写有该运动员终点城市的名字。每位运动员的终点是随机选定的，但不能与其起点城市相同。允许多名运动员在同一城市结束比赛。所有运动员同时起跑，并均沿起点到终点之间的最短路径奔跑，且所有人奔跑速度均为 $1$。

比赛结束后，将根据运动员完成路程所用时间的非降序排列生成一份成绩表。成绩表中前 $g$ 名运动员将获得金牌，接下来的 $s$ 名将获得银牌，其余运动员则获得铜牌。此外，若两名或以上运动员完成路程所用时间相同，则按其起点城市编号升序排列。这意味着不会出现并列名次。

根据比赛规则，金牌数量 $g$ 必须满足不等式 $g_1 \leq g \leq g_2$，其中 $g_1$ 与 $g_2$ 是历史上形成的固定值；类似地，银牌数量 $s$ 必须满足不等式 $s_1 \leq s \leq s_2$，其中 $s_1$ 与 $s_2$ 同样是历史上形成的固定值。

目前，在比赛尚未开始时，每位运动员的终点城市尚属未知。然而媒体迫切要求细节信息，因此你被委派计算奖牌分配方案的总数。若至少有一名运动员在两种方案中获得不同种类的奖牌，则认为这两种奖牌分配方案不同。

The first input line contains given integers n and m (3 ≤ n ≤ 50, n - 1 ≤ m ≤ 1000), where n is the number of Berland towns and m is the number of roads.

Next in m lines road descriptions are given as groups of three integers v, u, c, which are the numbers of linked towns and its length (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ c ≤ 1000). Every pair of cities have no more than one road between them.

The last line contains integers _g_1, _g_2, _s_1, _s_2 (1 ≤ _g_1 ≤ _g_2, 1 ≤ _s_1 ≤ _s_2, _g_2 + _s_2 < n). The input data numbers, located on one line, are space-separated.

第一行输入包含两个整数 $n$ 和 $m$（$3 \leq n \leq 50$，$n-1 \leq m \leq 1000$），其中 $n$ 表示 Berland 的城镇数量，$m$ 表示道路数量。

接下来的 $m$ 行中，每行给出一条道路的描述，格式为三个整数 $v$、$u$、$c$，分别表示相连的两个城镇编号及其长度（$1 \leq v, u \leq n$，$v \neq u$，$1 \leq c \leq 1000$）。任意两个城市之间至多只有一条道路。

最后一行包含四个整数 $g_1$、$g_2$、$s_1$、$s_2$（满足 $1 \leq g_1 \leq g_2$，$1 \leq s_1 \leq s_2$，且 $g_2 + s_2 < n$）。同一行中的输入数据以空格分隔。

Print the single number — the number of ways to distribute the medals. It is guaranteed that the number fits in the standard 64-bit signed data type.

输出一个整数——即分配奖牌的方式数目。保证该数在标准的 64 位有符号数据类型范围内。