A country called Berland consists of n cities, numbered with integer numbers from 1 to n. Some of them are connected by bidirectional roads. Each road has some length. There is a path from each city to any other one by these roads. According to some Super Duper Documents, Berland is protected by the Super Duper Missiles. The exact position of the Super Duper Secret Missile Silos is kept secret but Bob managed to get hold of the information. That information says that all silos are located exactly at a distance l from the capital. The capital is located in the city with number s.

The documents give the formal definition: the Super Duper Secret Missile Silo is located at some place (which is either city or a point on a road) if and only if the shortest distance from this place to the capital along the roads of the country equals exactly l.

Bob wants to know how many missile silos are located in Berland to sell the information then to enemy spies. Help Bob.

Input

The first line contains three integers n, m and s (2 ≤ n ≤ 105, <image>, 1 ≤ s ≤ n) — the number of cities, the number of roads in the country and the number of the capital, correspondingly. Capital is the city no. s. 

Then m lines contain the descriptions of roads. Each of them is described by three integers vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 1 ≤ wi ≤ 1000), where vi, ui are numbers of the cities connected by this road and wi is its length. The last input line contains integer l (0 ≤ l ≤ 109) — the distance from the capital to the missile silos. It is guaranteed that: 

  * between any two cities no more than one road exists; 
  * each road connects two different cities; 
  * from each city there is at least one way to any other city by the roads. 

Output

Print the single number — the number of Super Duper Secret Missile Silos that are located in Berland.

Examples

Input

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


Output

3


Input

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


Output

3

Note

In the first sample the silos are located in cities 3 and 4 and on road (1, 3) at a distance 2 from city 1 (correspondingly, at a distance 1 from city 3).

In the second sample one missile silo is located right in the middle of the road (1, 2). Two more silos are on the road (4, 5) at a distance 3 from city 4 in the direction to city 5 and at a distance 3 from city 5 to city 4.
import java.util.*;

/**
 * User: hornswf
 * Date: 3/17/12
 * Time: 5:14 PM
 */
public class MissileSilos {

    static final int inf = Integer.MAX_VALUE;

    /*represents an adjacency in a graph. Says to which node does it lead and what it's cost*/
    static class Adjacency implements Comparable<Adjacency>{
        int cost;
        int node;

        Adjacency(int cost, int node) {
            this.node = node;
            this.cost = cost;
        }

        public int compareTo(Adjacency other){
            if (this.cost > other.cost) return 1;
            if (this.cost < other.cost) return -1;
            return 0;
        }
    }



    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();
        int capital = s.nextInt();

        /*adjacency list. Nodes are represented by indexes in the array [0..n-1], so all edges in each cell of array
        goes from node number (array cell index)
        */
        ArrayList<ArrayList<Adjacency>> g = new ArrayList<ArrayList<Adjacency>>();

        for (int i = 0; i < n; i++) g.add(new ArrayList<Adjacency>());
        for (int i = 0; i < m; i++) {
            int st = s.nextInt() - 1; // different conventions
            int fi = s.nextInt() - 1; // [1...n] -> [0..(n-1)]
            int length = s.nextInt();

            Adjacency ad1 = new Adjacency(length, fi);
            Adjacency ad2 = new Adjacency(length, st);

            g.get(st).add(ad1);
            g.get(fi).add(ad2);

        }
        boolean[] visited = new boolean[n]; //serves dijkstra's search purposes
        int[] shortestDistances = new int[n]; //serves dijkstra's search purposes
        for (int i = 0;i < n; i++) shortestDistances[i] = inf; //from the very beginning it's very long to go to any node

        PriorityQueue<Adjacency> priorityQueue = new PriorityQueue<Adjacency>(); //serves dijkstra purposes

        priorityQueue.add(new Adjacency(0, capital-1)); //first node to be looked at, with known shortest distance value to it
        shortestDistances[capital-1] = 0; //capital is the center

        int distance = s.nextInt(); //distance from capital to missile silos

        /* *
        * standard dijkstra algorithm with addition of one condition:
        * we won't try to find shortest paths for those vertices, where there's shortest path is gonna be longer than
        * missile silos distance (all missiles would be found before we reach those cities)
        * */
        while (!priorityQueue.isEmpty()) {
            Adjacency adjacency = priorityQueue.poll();
            if (visited[adjacency.node]) continue;
            visited[adjacency.node]= true;
            for (Adjacency ad : g.get(adjacency.node)) {
                int newPossiblePathCost = adjacency.cost + ad.cost;
                if (newPossiblePathCost <= distance && newPossiblePathCost < shortestDistances[ad.node]) {
                    shortestDistances[ad.node] = newPossiblePathCost;
                    priorityQueue.add(new Adjacency(newPossiblePathCost, ad.node));

                }
            }
        }

        /* *
         * counts the number of missile silos
         * */
        int number = 0;
        for (int i=0;i<n;i++) {
            if (shortestDistances[i] != inf) { // if it's in the city, great! (well, no for the people, living in it, maybe)
                if (shortestDistances[i] == distance) {
                    number++;
                    continue;
                }
                for (Adjacency ad : g.get(i)) {
                    int newPossiblePathCost = shortestDistances[i] + ad.cost;
                    /* *
                     * if from this city exist any edge, that, summed with the shortest distance value of the city, is bigger
                     * than the distance to the missile - missile is somewhere on that edge
                     * */
                    if (newPossiblePathCost > distance) {
                        int middlePoint = shortestDistances[ad.node] + ad.cost - (distance - shortestDistances[i]);
                        if (shortestDistances[ad.node] == inf) number++; // if the city wasn't discovered - it's too far, and
                                                                         // and the missile's gonna be on the road to it
                        else if (distance < middlePoint) number++; // if it's closer to the current node, than to it's neighbour
                        else if ((distance == middlePoint) && i < ad.node) number++; // if it's right in the middle - make sure to
                                                                                     // to count it only once
                    }
                }

            }
        }

        System.out.println(number);


    }
}
