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.*;
import java.math.BigInteger;
import java.util.*;

import javax.swing.plaf.synth.SynthSpinnerUI;
public class Problem2 {
	static Scanner sc=new Scanner(System.in);
	static final double EPS = 1e-9;
	static ArrayList<Integer> adj[];
	static boolean railway[][];
	static int dx[] = {1,1,0,-1,-1,-1, 0, 1};
	static int dy[] = {0,1,1, 1, 0,-1,-1,-1};
	static  HashSet<Pair> set;
	public static void main(String[] args) throws IOException, InterruptedException {
		 PrintWriter out=new PrintWriter(System.out);
		V=sc.nextInt();
		int e=sc.nextInt();
		int s=sc.nextInt()-1;
		  adjList = new ArrayList[V];
	        for(int i = 0; i < V; ++i)
	            adjList[i] = new ArrayList<>();
		while(e-->0) {
			int u=sc.nextInt()-1;
			int v=sc.nextInt()-1;
			int w=sc.nextInt();
			adjList[u].add(new Edge(v, w));
            adjList[v].add(new Edge(u, w));
		}
	
		int l=sc.nextInt();
		long dist[]=new long[V];
		Arrays.fill(dist,INF);
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.add(new Edge(s, 0));
		dist[s]=0;
		while(!pq.isEmpty()) {
			Edge cur=pq.poll();
			
			if(cur.cost>dist[cur.node]) {
				continue;
			}
			
			for(Edge nxt: adjList[cur.node]) {
			
				if(cur.cost + nxt.cost < dist[nxt.node])
					pq.add(new Edge(nxt.node, dist[nxt.node] = cur.cost + nxt.cost ));
			
			}
			
		}
		int ans=0;
		for(int i=0 ; i<V; i++) {
	        if(dist[i] == l)
	        	ans++;
            else if (dist[i] < l) 
		for(Edge x:adjList[i]) {
			if(dist[i]+x.cost>l) {
				
			
			long dis= dist[x.node]+x.cost-(l-dist[i]);
			if(dis<l||(dis==l&&i>x.node)) {
				continue;
			}
				ans++;
			
			}
		
		}
            
		}
		System.out.println(ans);
		
	
	}
	static  TreeMap<Pair,Integer> map;
	static int cap=(int) 1e9;
	
	static class Pair implements Comparable<Pair>{
		int u;
		int v;
		public Pair(int u1,int v1) {
			u=u1;
			v=v1;
		}

		public int compareTo(Pair p) {
			if (u - p.u == 0)
				return v - p.v;
			return u- p.u;
		}
	}
	static int n1;
	static  boolean visited[];
	
	static final long INF = (long)1e19;	//don't increase, avoid overflow
	static ArrayList<Edge>[] edgejList;
	static HashSet<Long> set1[];
	static ArrayList<Edge>[] adjList;
	static int V;
	
	/*
	 * 1. Dijkstra's Algorithm for SSSP on weighted graphs
	 */
	static long dijkstra(int S, int T)	//O(E log E)
	{
			
		return -1;
	}
	static class Edge implements Comparable<Edge>
	{
		int node; long cost;
		
		Edge(int a, long l) { node = a;	cost = l; }
		
		public int compareTo(Edge e){ return (int) (cost - e.cost);	}
	}
	/**static int kruskal()		//O(E log E)
	{
		int mst = 0;
		Arrays.sort(edgeList);
		UnionFind uf = new UnionFind(V);

		for(Edge e: edgeList)
			if(uf.union(e.node, e.v))
				mst += e.w;
		return mst;
	}**/

	
	static class UnionFind {                                              
		int[] p, rank;

		UnionFind(int N) 
		{
			p = new int[N];
			rank = new int[N];
			for (int i = 0; i < N; i++) 
				p[i] = i;
		}

		int findSet(int x) { return p[x] == x ? x : (p[x] = findSet(p[x])); }

		boolean union(int x, int y) 
		{ 
			x = findSet(x);
			y = findSet(y);
			if(x == y)
				return false;

			if (rank[x] > rank[y]) 
				p[y] = x;
			else
			{	
				p[x] = y;
				if(rank[x] == rank[y])
					++rank[y]; 
			} 
			return true;
		}
	}
	static int numPF(int N)
	{
		int ans = 0, idx = 0, p = primes.get(0);
		while(p * p <= N)
		{
			while(N % p == 0) { N /= p; ++ans; }
			p = primes.get(++idx);
		}
		if(N != 1)
			++ans;
		return ans;
	}
	static ArrayList<Integer> div=new ArrayList<>();

	static boolean Limit(int b, int e)	
	{
		return b + EPS < Math.pow(2, 64.0 / e);
	}
	static int numDivs(int N)
	{
		int ans = 0;
		for(int i = 1; i * i <= N; ++i)
			if(N % i == 0)
			{
				++ans;
				
				if(N / i != i) 
					++ans;
				
			}
		return ans;
	}
	static boolean isPrime(int N)
	{
		if(N <= 1e6)
			return !isComposite[N];
		for(int p: primes)
			if(p * p > N)
				break;
			else if(N % p == 0)
				return false;
		return true;
	}
	static ArrayList<Integer> primes;
	static TreeSet<Integer> primes1;
	static HashMap<Integer,Integer> prime;
	static boolean[] isComposite;
	static int primus[]=new int[664579];
	static void sieve(int N)	// O(N log log N) 
	{
		isComposite = new boolean[N+1];					
		isComposite[0] = isComposite[1] = true;			// 0 indicates a prime number
		primes = new ArrayList<Integer>();
		primes1=new TreeSet<>();
		int nxt = 0;
        for (int i = 2; i <= N; ++i) 					//can loop till i*i <= N if primes array is not needed O(N log log sqrt(N)) 
			if (isComposite[i] == false) 					//can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i); 
				primes1.add(i);
				primus[nxt++] = i;
				if(1l * i * i <= N)
					for (int j = i * i; j <= N; j += i)	// j = i * 2 will not affect performance too much, may alter in modified sieve
						isComposite[j] = true;
			}   
	}

static	 class Scanner {
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s) {
		br = new BufferedReader(new InputStreamReader(s));
	}

	public String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	public int[] nextIntArr(int n) throws IOException {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextInt();
		return arr;
	}

	public long[] nextLongArr(int n) throws IOException {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextLong();
		return arr;
	}

	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	public String nextLine() throws IOException {
		return br.readLine();
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	public boolean ready() throws IOException {
		return br.ready();
	}
	public void waitForInput() throws InterruptedException {Thread.sleep(2000);}
}
	
}
 class Dsu {
	int[] p, rank, setSize;
	int numSets;

	public Dsu(int N) 
	{
		
		numSets = N;
		p = new int[N];
		rank = new int[N];
		setSize = new int[N];
		Arrays.fill(setSize, 1);
		for (int i = 0; i < N; i++) 
			p[i] = i; 
	
	}

	public int findSet(int v) { 
		if (v == p[v])
        return v;
		
    return findSet(p[v]);
	}

	public boolean isSameSet(int i, int j) { return findSet(i) == findSet(j); }

	public void unionSet(int i, int j) 
	{ 
		if (isSameSet(i, j)) 
			return;
		numSets--; 
		int x = findSet(i), y = findSet(j);
		if(setSize[x] > setSize[y]) { 
		p[y] = x;
		setSize[x] += setSize[y]; 
		}
		else
		{	p[x] = y;
		setSize[y] += setSize[x];
		} 
	}

	public int numDisjointSets() { return numSets; }

	public int sizeOfSet(int i) { return setSize[findSet(i)]; }
}




 