{"raw_statement":[{"iden":"statement","content":"JOI 国有 $N$ 个火车站，编号从 $1$ 到 $N$。另外，JOI 国有 $M$ 条双向铁路线，编号从 $1$ 到 $M$。铁路线 $i\\ (1 \\leq i \\leq M)$ 连接了火车站 $A_{i}$ 和火车站 $B_{i}$，从一个站到另一个站需要花费 $C_i$ 分钟。\n\n你是 JOI 国的部长，决定按照以下方式新建一条铁路线：\n\n选择两个整数 $u, v\\ (1 \\leq u<v \\leq N)$，在火车站 $u$ 和火车站 $v$ 之间建设一条双向铁路线，从一个站到另一个站需要花费 $L$ 分钟。注意，即使已经有一条连接火车站 $u$ 和火车站 $v$ 的铁路线也可以建设。\n\n如果你建设这条铁路线后，可以花费不超过 $K$ 分钟从火车站 $S$ 到火车站 $T$，国王就会高兴。我们不考虑换乘时间和等待时间。\n\n你有 $\\frac{N(N-1)}{2}$ 种选择两个整数 $u, v$ 的方法，你想知道其中有多少种方法会让国王高兴。\n\n给定火车站和铁路线以及国王的要求的信息，编写一个程序，求出其中有多少种选择整数的方法会让国王高兴。"},{"iden":"input","content":"第一行包含两个整数 $N,M$。\n\n第二行包含四个整数 $S,T,L,K$。\n\n接下来 $M$ 行，每行包含三个整数 $A_i, B_i, C_i$，表示第 $i$ 条双向铁路线。"},{"iden":"output","content":"输出一行一个整数，表示让国王高兴的两个整数的选择方法有多少种。"},{"iden":"note","content":"对于所有输入数据，满足：\n\n- $2 \\leq N \\leq 2\\times 10^5$\n- $1 \\leq M \\leq 2\\times 10^5$\n- $1 \\leq S<T \\leq N$\n- $1 \\leq L \\leq 10^{9}$\n- $1 \\leq K \\leq 10^{15}$\n- $1 \\leq A_{i}<B_{i} \\leq N\\ (1 \\leq i \\leq M)$\n- $(A_{i}, B_{i}) \\neq (A_{j}, B_{j})\\ (1 \\leq i<j \\leq M)$\n- $1 \\leq C_{i} \\leq 10^{9}\\ (1 \\leq i \\leq M)$\n\n详细子任务附加限制及分值如下表所示。\n\n|子任务|\t附加限制|\t分值|\n|:-:|:-:|:-:|\n|1|\t$L=1, K=2, C_{i}=1\\ (1 \\leq i \\leq M)$|\t8\n|2|\t$N \\leq 50, M \\leq 50$|\t16\n|3|\t$N \\leq 3000, M \\leq 3000$|\t29\n|4|\t无附加限制|\t47"}],"translated_statement":null,"sample_group":[["7 8\n6 7 1 2\n1 2 1\n1 6 1\n2 3 1\n2 4 1\n3 5 1\n3 7 1\n4 5 1\n5 6 1","4"],["3 2\n1 3 1 2\n1 2 1\n2 3 1","3"],["6 4\n2 5 1000000000 1\n1 2 1000000000\n2 3 1000000000\n2 4 1000000000\n5 6 1000000000","0"],["18 21\n4 8 678730772 3000000062\n5 13 805281073\n8 17 80983648\n3 8 996533440\n10 16 514277428\n2 5 57914340\n6 11 966149890\n8 12 532734310\n2 9 188599710\n2 3 966306014\n12 16 656457780\n16 18 662633078\n1 15 698078877\n2 8 665665772\n2 6 652261981\n14 15 712798281\n7 13 571169114\n13 14 860543313\n6 7 454251187\n9 14 293590683\n6 14 959532841\n3 11 591245645","16"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}