题目描述

最近《绝地求生：大逃杀》风靡全球，皮皮和毛毛也迷上了这款游戏，他们经常组队玩这款游戏。

在游戏中，皮皮和毛毛最喜欢做的事情就是堵桥，每每有一个好时机都能收到不少的快递。

当然，有些时候并不能堵桥，皮皮和毛毛会选择在其他的必经之路上蹲点。

K 博士作为一个老年人，外加有心脏病，自然是不能玩这款游戏的，但是这并不能妨碍他对这款游戏进行一些理论分析，比如最近他就对皮皮和毛毛的战士很感兴趣。

游戏的地图可以抽象为一张 $n$ 个点 $m$ 条无向边的图，节点编号为 $1$ 到 $n$ ，每条边具有一个正整数的长度。

假定大魔王都会从 $S$ 点出发到达 $T$ 点（$S$ 和 $T$ 已知），并且只会走最短路，皮皮和毛毛会在 $A$ 点和 $B$ 点埋伏大魔王。

为了保证一定能埋伏到大魔王，同时又想留大魔王一条生路，皮皮和毛毛约定 $A$ 点和 $B$ 点必须满足：

1. 大魔王所有可能路径中，必定会经过 $A$ 点和 $B$ 点中的任意一点
2. 大魔王所有可能路径中，不存在一条路径同时经过 $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

数据范围与提示

$1 \le n \le 5 \times 10^4, 1 \le m \le 5 \times 10^4, 1 \le w \le 10^9$

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/陈宇　命题/陈宇　验题/邢健开
Git Repo：https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。