CF38H The Great Marathon

- 在一个 $n$ 个点，$m$ 条边的无向连通图（有边权）上，有 $n$ 个运动员参加马拉松。 - 第 $i$ 个运动员起点为 $i$ 号点，每个运动员有自己的终点，终点可以为起点外的任何一点，多个运动员可以对应同一个终点。 - 每个运动员走最短路径抵达终点，用时为途径边权和。计算排名时，用时短的靠前；用时一样则起点编号小的靠前。 - 选择两个数 $g\in [g_1,g_2]，s\in [s_1,s_2]$。取第 $1$ 到第 $g$ 名为金牌，第 $g+1$ 到第 $g+s$ 名为银牌，其余为铜牌。 - 求一共有多少种不同的奖牌分配方案。两个方案不同当且仅当至少有一人获得的奖牌不同。保证答案在 $64$ 位有符号整数的范围内。

第一行两个整数 $n$ 和 $m$。$(3\le n\le 50, n-1\le m\le 1000)$ 接下来 $m$ 行，每行三个整数 $u,v,c$，表示 $u$ 和 $v$ 间有条长度 $c$ 的无向边。无重边、自环。$(1\le u,v\le n,u\neq v,1\le c\le 1000)$ 最后一行四个整数 $g_1,g_2,s_1,s_2$。$(1\le g_1\le g_2,1\le s_1\le s_2, g_2+s_2

一行一个整数，表示方案数。