题目描述
JOI 国有 N 个火车站,编号从 1 到 N。另外,JOI 国有 M 条双向铁路线,编号从 1 到 M。铁路线 i (1≤i≤M) 连接了火车站 Ai 和火车站 Bi,从一个站到另一个站需要花费 Ci 分钟。
你是 JOI 国的部长,决定按照以下方式新建一条铁路线:
选择两个整数 u,v (1≤u<v≤N),在火车站 u 和火车站 v 之间建设一条双向铁路线,从一个站到另一个站需要花费 L 分钟。注意,即使已经有一条连接火车站 u 和火车站 v 的铁路线也可以建设。
如果你建设这条铁路线后,可以花费不超过 K 分钟从火车站 S 到火车站 T,国王就会高兴。我们不考虑换乘时间和等待时间。
你有 2N(N−1) 种选择两个整数 u,v 的方法,你想知道其中有多少种方法会让国王高兴。
给定火车站和铁路线以及国王的要求的信息,编写一个程序,求出其中有多少种选择整数的方法会让国王高兴。
输入格式
第一行包含两个整数 N,M。
第一行包含两个整数 S,T,L,K。
接下来 M 行,每行包含三个整数 Ai,Bi,Ci,表示第 i 条双向铁路线。
输出格式
输出一行一个整数,表示让国王高兴的两个整数的选择方法有多少种。
提示
对于所有输入数据,满足:
- 2≤N≤2×105
- 1≤M≤2×105
- 1≤S<T≤N
- 1≤L≤109
- 1≤K≤1015
- 1≤Ai<Bi≤N (1≤i≤M)(Ai,Bi)=(Aj,Bj) (1≤i<j≤M)
- 1≤Ci≤109 (1≤i≤M)
详细子任务附加限制及分值如下表所示。
子任务 |
附加限制 |
分值 |
1 |
L=1,K=2,Ci=1 (1≤i≤M) |
8 |
2 |
N≤50,M≤50 |
16 |
3 |
N≤3000,M≤3000 |
29 |
4 |
无附加限制 |
47 |