Geralt is currently chasing the Wild Hunt and has now reached Nilfgaard. Nilfgaard consists of n cities connected by a network of m roads. Also, one can reach any city from any other city. He is currently in city s. He has been informed that the Wild Hunt has planted some magical explosives at certain locations which surprisingly (but more importantly, due to the demand of question :P) are all at those points which are having their shortest distance from city s equal to l (That's why they are "magical" :P). These locations can either be a city or some point on some road. Geralt has asked you to calculate that how many locations are there which are at a shortest distance of l from city s.
Note: Shortest Distance equal to l means that the lenght of shortest path to that point from city s should be equal to l.
Cities are numbered from 1 to n.
Input Format--
First line consists of n, m and s, number of cities, number of roads and the source city respectively.
Each of the next m lines consists of u, v and w, denoting that the cities numbered u and v are linked by a road having length w.
Last line consists of l, the distance between explosives and city s.
Output Format--
Output one integer denoting the number of magical explosives.
Constraints--
1≤n≤105
n−1≤m≤min(105,n∗(n−1)/2)
1≤s≤n
1≤u,v≤n
1≤w≤104
1≤l≤109
Magical explosives are located at cities 3 and 4 and at the road joining cities 1 and 3 at distance 2 from city 1 (and at distance 1 from city 3).