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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;


public class MissileSilos 
{

	public static void main(String[] args) throws IOException 
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String [] data = in.readLine().split(" ");
		int n = Integer.parseInt(data[0]);
		int m = Integer.parseInt(data[1]);
		int s = Integer.parseInt(data[2]);
		
		LinkedList<WeiEdge>[] adyacencia = (LinkedList<WeiEdge>[]) new LinkedList<?>[n+1];
		LinkedList<WeiEdge> edges = new LinkedList<WeiEdge>();
		for (int i = 0; i<n+1;++i)
			adyacencia[i] = new LinkedList<WeiEdge>();
		
		for (int i = 1;i<=m; ++i)
		{
			data = in.readLine().split(" ");
			int u = Integer.parseInt(data[0]);
			int v = Integer.parseInt(data[1]);
			int w = Integer.parseInt(data[2]);
			adyacencia[v].add(new WeiEdge(u,v,w));
			adyacencia[u].add(new WeiEdge(u,v,w));
			edges.add(new WeiEdge(u,v,w));
		}

		int l = Integer.parseInt(in.readLine());
		
		
		
		int [] distTo = new int[n+1];
		int [] edgeTo = new int[n+1];
		Arrays.fill(distTo, Integer.MAX_VALUE/2-1);
		distTo[s] = 0;
		IndexMinPQ2<Integer> cola = new IndexMinPQ2<Integer>(n+1);
		cola.insert(s, distTo[s]);
		while(!cola.isEmpty())
		{
			int minVertex = cola.delMin();
			for (WeiEdge ady: adyacencia[minVertex])
			{
				int other = ady.u+ady.v-minVertex;
				if (distTo[other] > distTo[minVertex] + ady.weight) 
				{
		            distTo[other] = distTo[minVertex] + ady.weight;
		            edgeTo[other] = minVertex;
		            if (!cola.contains(other))
		            {
		            	cola.insert(other, distTo[other]);
		            }
		            else
		            	cola.decreaseKey(other, distTo[other]);
		        }
			}
		}
		
		int t = 0;
		boolean [] processed = new boolean[n+1];
		for (WeiEdge e : edges)
		{
			if (!processed[e.u])
			{
				processed[e.u] = true;
				if (distTo[e.u] == l) ++t;
			}
			if (!processed[e.v])
			{
				processed[e.v] = true;
				if (distTo[e.v] == l) ++t;
			}
			
			if (l>distTo[e.v] && l<distTo[e.v] + e.weight && 2*l < e.weight +distTo[e.u]+distTo[e.v]) {
				++t;
			}
			if (l>distTo[e.u] && l<distTo[e.u] + e.weight && 2*l <= e.weight +distTo[e.u]+distTo[e.v]) {
				++t;
			}
		}
		System.out.println(t);
	}
}
class WeiEdge
{
	public int weight;
	public int v;
	public int u;
	public WeiEdge(int u, int v, int weight)
	{
		this.u = u;
		this.v = v;
		this.weight = weight;
	}
}

/*************************************************************************
 *  Compilation:  javac IndexMinPQ.java
 *  Execution:    java IndexMinPQ
 *
 *  Minimum-oriented indexed PQ implementation using a binary heap.
 *
 *********************************************************************/

/**
 *  The <tt>IndexMinPQ</tt> class represents an indexed priority queue of generic keys.
 *  It supports the usual <em>insert</em> and <em>delete-the-minimum</em>
 *  operations, along with <em>delete</em> and <em>change-the-key</em> 
 *  methods. In order to let the client refer to keys on the priority queue,
 *  an integer between 0 and NMAX-1 is associated with each key&mdash;the client
 *  uses this integer to specify which key to delete or change.
 *  It also supports methods for peeking at the minimum key,
 *  testing if the priority queue is empty, and iterating through
 *  the keys.
 *  <p>
 *  This implementation uses a binary heap along with an array to associate
 *  keys with integers in the given range.
 *  The <em>insert</em>, <em>delete-the-minimum</em>, <em>delete</em>,
 *  <em>change-key</em>, <em>decrease-key</em>, and <em>increase-key</em>
 *  operations take logarithmic time.
 *  The <em>is-empty</em>, <em>size</em>, <em>min-index</em>, <em>min-key</em>, and <em>key-of</em>
 *  operations take constant time.
 *  Construction takes time proportional to the specified capacity.
 *  <p>
 *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/24pq">Section 2.4</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
class IndexMinPQ2<Key extends Comparable<Key>>{
    private int NMAX;        // maximum number of elements on PQ
    private int N;           // number of elements on PQ
    private int[] pq;        // binary heap using 1-based indexing
    private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
    private Key[] keys;      // keys[i] = priority of i

    /**
     * Initializes an empty indexed priority queue with indices between 0 and NMAX-1.
     * @param NMAX the keys on the priority queue are index from 0 to NMAX-1
     * @throws java.lang.IllegalArgumentException if NMAX < 0
     */
    public IndexMinPQ2(int NMAX) {
        if (NMAX < 0) throw new IllegalArgumentException();
        this.NMAX = NMAX;
        keys = (Key[]) new Comparable[NMAX + 1];    // make this of length NMAX??
        pq   = new int[NMAX + 1];
        qp   = new int[NMAX + 1];                   // make this of length NMAX??
        for (int i = 0; i <= NMAX; i++) qp[i] = -1;
    }

    /**
     * Is the priority queue empty?
     * @return true if the priority queue is empty; false otherwise
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * Is i an index on the priority queue?
     * @param i an index
     * @throws java.lang.IndexOutOfBoundsException unless (0 &le; i < NMAX)
     */
    public boolean contains(int i) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        return qp[i] != -1;
    }

    /**
     * Returns the number of keys on the priority queue.
     * @return the number of keys on the priority queue
     */
    public int size() {
        return N;
    }

    /**
     * Associates key with index i.
     * @param i an index
     * @param key the key to associate with index i
     * @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
     * @throws java.util.IllegalArgumentException if there already is an item associated with index i
     */
    public void insert(int i, Key key) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
        N++;
        qp[i] = N;
        pq[N] = i;
        keys[i] = key;
        swim(N);
    }

    /**
     * Returns an index associated with a minimum key.
     * @return an index associated with a minimum key
     * @throws java.util.NoSuchElementException if priority queue is empty
     */
    public int minIndex() { 
        return pq[1];        
    }

    /**
     * Returns a minimum key.
     * @return a minimum key
     * @throws java.util.NoSuchElementException if priority queue is empty
     */
    public Key minKey() { 
        return keys[pq[1]];        
    }

    /**
     * Removes a minimum key and returns its associated index.
     * @return an index associated with a minimum key
     * @throws java.util.NoSuchElementException if priority queue is empty
     */
    public int delMin() { 
        int min = pq[1];        
        exch(1, N--); 
        sink(1);
        qp[min] = -1;            // delete
        keys[pq[N+1]] = null;    // to help with garbage collection
        pq[N+1] = -1;            // not needed
        return min; 
    }

    /**
     * Returns the key associated with index i.
     * @param i the index of the key to return
     * @return the key associated with index i
     * @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
     * @throws java.util.NoSuchElementException no key is associated with index i
     */
    public Key keyOf(int i) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        else return keys[i];
    }

    /**
     * Change the key associated with index i to the specified value.
     * @param i the index of the key to change
     * @param key change the key assocated with index i to this key
     * @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
     * @deprecated Replaced by changeKey()
     */
    @Deprecated public void change(int i, Key key) {
        changeKey(i, key);
    }

    /**
     * Change the key associated with index i to the specified value.
     * @param i the index of the key to change
     * @param key change the key assocated with index i to this key
     * @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
     * @throws java.util.NoSuchElementException no key is associated with index i
     */
    public void changeKey(int i, Key key) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }

    /**
     * Decrease the key associated with index i to the specified value.
     * @param i the index of the key to decrease
     * @param key decrease the key assocated with index i to this key
     * @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
     * @throws java.lang.IllegalArgumentException if key &ge; key associated with index i
     * @throws java.util.NoSuchElementException no key is associated with index i
     */
    public void decreaseKey(int i, Key key) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (keys[i].compareTo(key) <= 0) throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
        keys[i] = key;
        swim(qp[i]);
    }

    /**
     * Increase the key associated with index i to the specified value.
     * @param i the index of the key to increase
     * @param key increase the key assocated with index i to this key
     * @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
     * @throws java.lang.IllegalArgumentException if key &le; key associated with index i
     * @throws java.util.NoSuchElementException no key is associated with index i
     */
    public void increaseKey(int i, Key key) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        if (keys[i].compareTo(key) >= 0) throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
        keys[i] = key;
        sink(qp[i]);
    }

    /**
     * Remove the key associated with index i.
     * @param i the index of the key to remove
     * @throws java.lang.IndexOutOfBoundsException unless 0 &le; i < NMAX
     * @throws java.util.NoSuchElementException no key is associated with index i
     */
    public void delete(int i) {
        if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
        int index = qp[i];
        exch(index, N--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }


   /**************************************************************
    * General helper functions
    **************************************************************/
    private boolean greater(int i, int j) {
        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
    }

    private void exch(int i, int j) {
        int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap;
        qp[pq[i]] = i; qp[pq[j]] = j;
    }


   /**************************************************************
    * Heap helper functions
    **************************************************************/
    private void swim(int k)  {
        while (k > 1 && greater(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

}

