CF144D Missile Silos

有一个叫做 Berland 的国家，由 $n$ 个城市组成，这些城市被编号为 $1$ 到 $n$ 的整数。一些城市之间由双向公路连接，每条公路有一定的长度。通过这些公路，每座城市都可以到达任意其他城市。 根据某些绝密文件，Berland 受到超级导弹的保护。超级秘密导弹发射井的确切位置被严格保密，但 Bob 设法拿到了相关情报。情报显示，所有发射井都位于距离首都恰好为 $l$ 的地方。首都位于编号为 $s$ 的城市。 文件中给出了严格的定义：如果某个位置（可以是某座城市，也可以是公路上的某点）到首都沿公路的最短距离恰好等于 $l$，那么该位置就是超级秘密导弹发射井的位置。 Bob 想知道 Berland 一共存在多少个这样的发射井位置，以便出售给敌国间谍。请你帮 Bob 计算一下。

第一行包含三个整数 $n$、$m$ 和 $s$（$2\leq n \leq 10^5$，$1\leq m \leq 10^5$，$1\leq s \leq n$），分别表示城市数量、公路数量和首都城市编号。 接下来 $m$ 行，每行包含三个整数 $v_i$、$u_i$、$w_i$（$1\leq v_i, u_i \leq n$，$v_i \ne u_i$，$1\leq w_i \leq 1000$），表示一条长度为 $w_i$ 的公路连接了城市 $v_i$ 和 $u_i$。 输入的最后一行为一个整数 $l$（$0\leq l \leq 10^9$），表示发射井到首都的距离。 保证： - 任意两座城市之间最多只有一条公路； - 每条公路连接两座不同的城市； - 任意两座城市之间至少存在一条路径。

输出一个整数，表示 Berland 中超级秘密导弹发射井的位置数量。

在第一个样例中，发射井分别位于城市 $3$ 和 $4$，以及公路 $(1,3)$ 上距离城市 $1$ 为 $2$ 的位置（即距离城市 $3$ 为 $1$ 的位置）。 在第二个样例中，有一个发射井正好位于公路 $(1,2)$ 的中点。另外两个发射井分别在公路 $(4,5)$ 上，分别距离城市 $4$ 和城市 $5$ 各为 $3$ 的位置。 由 ChatGPT 5 翻译