一个名为 Berland 的国家由 n 个城市组成,城市编号为 1 到 n 的整数。其中一些由双向道路连接。每条路都有一定的长度。通过这些道路,从每个城市到任何其他城市都有一条路径。根据一些超级杜珀文件,伯兰德受到超级杜珀导弹的保护。超级骗子秘密导弹发射井的确切位置一直保密,但鲍勃设法掌握了该信息。该信息表明,所有筒仓都位于距首都 l 处。首都位于编号为s的城市。
文件给出了正式的定义:超级秘密导弹发射井位于某个地方(可以是城市,也可以是道路上的一个点),当且仅当沿着该国道路从这个地方到首都的最短距离恰好等于l。
鲍勃想知道伯兰德有多少个导弹发射井,以便将信息出售给敌方间谍。帮助鲍勃。
输入
第一行包含三个整数 n、m 和 s (2 ≤ n ≤ 105, $$n-1 \leq m \leq \min(10^5, \frac{n(n-1)}{2})$$, 1 ≤ s ≤ n) — 相应地,城市数量、国家道路数量和首都数量。首都是城市编号。 s。
然后 m 行包含道路的描述。每条道路均由三个整数 vi、ui、wi(1 ≤ vi、ui ≤ n、vi ≠ ui、1 ≤ wi ≤ 1000)描述,其中 vi、ui 是该道路所连接城市的编号,wi 是该道路的长度。最后输入行包含整数 l (0 ≤ l ≤ 109) — 从首都到导弹发射井的距离。保证:
- 任意两个城市之间不存在超过一条道路;
- 每条道路连接两个不同的城市;
- 从每个城市至少有一条路可以通过公路到达任何其他城市。
输出
打印单个数字 — 位于 Berland 的 Super Duper 秘密导弹发射井的数量。
示例
输入 #1
4 6 1 1 2 1 1 3 3 2 3 1 2 4 1 3 4 1 1 4 2 2
输出 #1
3
输入 #2
5 6 3 3 1 1 3 2 1 3 4 1 3 5 1 1 2 6 4 5 8 4
输出 #2
3
注意
在第一个样本中,筒仓位于城市 3 和 4 以及道路 (1, 3) 上,距城市 1 的距离为 2(相应地,距城市 3 的距离为 1)。
在第二个样本中,一个导弹发射井位于道路中间 (1, 2)。道路 (4, 5) 上还有两个筒仓,在前往城市 5 的方向上距城市 4 的距离为 3,以及从城市 5 到城市 4 的距离为 3。