游戏的地图可以抽象为一张 n 个点 m 条无向边的图，节点编号为 1 到 n，每条边具有一个正整数的长度。假定大魔王都会从 S 点出发到达 T 点（S 和 T 已知），并且只会走最短路，皮皮和毛毛会在 A 点和 B 点埋伏大魔王。为了保证一定能埋伏到大魔王，同时又想留大魔王一条生路，皮皮和毛毛约定 A 点和 B 点必须满足：大魔王所有可能路径中，必定会经过 A 点和 B 点中的任意一点；大魔王所有可能路径中，不存在一条路径同时经过 A 点和 B 点。K博士想知道，满足上面两个条件的 A,B 点对有多少个，交换 A,B 的顺序算相同的方案。
第一行输入四个整数 n,m,S,T(1 \le n \le 5 \times 10^{4}, 1 \le m \le 5 \times 10^{4}, 1 \le S,T \le n)，含义见题目描述。接下来输入 m 行，每行输入三个整数 u,v,w(1 \le u,v \le n, 1 \le w \le 10^{9}) 表示存在一条长度为 w 的边链接 u 和 v。
输出一行表示答案。
7 7 1 7 1 2 2 2 4 2 4 6 2 6 7 2 1 3 2 3 5 4 5 7 2
6
5 5 1 4 1 2 1 1 3 1 2 4 1 3 4 1 4 5 1
3
6 7 1 4 1 2 1 1 3 1 2 4 1 3 4 1 4 5 1 1 6 2 6 4 2
5
通过计算，不难得出合法的方案有 (2,3),(2,4),(4,3),(4,5),(6,3),(6,5)。
| 测试点编号 | n | m | w | 特殊性 |
|---|---|---|---|---|
| 1\sim2 | 1\le n\le200 | 1\le m\le200 | 1\le w\le10^9 | 输入数据是一条链，满足 m=n-1；对于每条边，满足 v=u+1 |
| 3\sim6 | ^ | ^ | ^ | 无 |
| 7\sim12 | 1\le n\le2000 | 1\le m\le2000 | ^ | ^ |
| 13\sim20 | 1\le n\le5\times10^4 | 1\le m\le5\times10^4 | ^ | ^ |