题目描述

Berland 国有 $n$ 座城市，编号 1 到 $n$，一些城市之间由双向道路相连，每条道路都有长度。沿道路可以从任意城市到达任意其他城市。根据某份"超级档案"，Berland 由"超级导弹"保护，而超级机密导弹发射井的确切位置是保密的——不过 Bob 搞到了情报：所有发射井都恰好位于距首都 $l$ 的地方。首都是编号为 $s$ 的城市。

档案给出了严格定义：某处位置（可以是城市，也可以是道路上的某一点）是超级机密导弹发射井，当且仅当它沿国家道路到首都的最短距离恰好等于 $l$。

Bob 想知道 Berland 有多少个导弹发射井，好把情报卖给敌方间谍。请帮帮他。

输入格式

第一行包含三个整数 $n$、$m$、$s$（$2 \le n \le 10^5$，$n-1 \le m \le \min(10^5, \frac{n(n-1)}{2})$，$1 \le s \le n$），分别表示城市数、道路数和首都编号。

接下来 $m$ 行描述道路，每行三个整数 $v_i$、$u_i$、$w_i$（$1 \le v_i, u_i \le n$，$v_i \ne u_i$，$1 \le w_i \le 1000$），其中 $v_i$、$u_i$ 是这条道路连接的两座城市编号，$w_i$ 是道路长度。最后一行包含整数 $l$（$0 \le l \le 10^9$），即首都到导弹发射井的距离。保证：

• 任意两座城市之间至多一条道路；
• 每条道路连接两座不同的城市；
• 沿道路可以从每座城市到达其他任意城市。

输出格式

输出一个数——Berland 境内超级机密导弹发射井的个数。

4 6 1
1 2 1
1 3 3
2 3 1
2 4 1
3 4 1
1 4 2
2

3

5 6 3
3 1 1
3 2 1
3 4 1
3 5 1
1 2 6
4 5 8
4

3