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.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class cf144d {

    public static void main(String[] args) throws IOException {
        int n = rni(), m = ni(), s = ni();
        Set<P> edges = new HashSet<>();
        List<List<spfa_P>> adj = new ArrayList<>();
        for(int i = 0; i < n; ++i) {
            adj.add(new ArrayList<>());
        }
        for(int i = 0; i < m; ++i) {
            int u = rni() - 1, v = ni() - 1, w = ni();
            P p = new P(u, v, w);
            edges.add(p);
            adj.get(u).add(new spfa_P(v, w));
            adj.get(v).add(new spfa_P(u, w));
        }
        int l = ri();
        int dist[] = spfa(s - 1, adj)[0], ans = 0;
        for(int i = 0; i < n; ++i) {
            if(dist[i] == l) {
                ++ans;
            }
        }
        for(P p : edges) {
            int maxdist = dist[p.a] + dist[p.b] + p.c;
            if(maxdist == 2 * l) {
                if(dist[p.a] < l && dist[p.b] < l) {
                    ++ans;
                }
            } else if(maxdist > 2 * l) {
                if(dist[p.a] < l) {
                    ++ans;
                    // prln(2, p.a, p.b);
                }
                if(dist[p.b] < l) {
                    ++ans;
                    // prln(3, p.a, p.b);
                }
            }
            // prln(p);
            // prln(maxdist);
        }
        prln(ans);
        close();
    }

    // spfa_P = {node, dist}
    static int[][] spfa(int src, List<List<spfa_P>> adjList) {
        return spfa(src, adjList, IBIG);
    }


    static int[][] spfa(int src, List<List<spfa_P>> adjList, int inf) {
        int n = adjList.size(), dist[] = new int[n], par[] = new int[n];
        fill(dist, inf);
        fill(par, -1);
        dist[src] = 0;
        Queue<spfa_P> q = new LinkedList<>();
        Set<Integer> s = new HashSet<>();
        q.offer(new spfa_P(src, 0));
        s.add(src);
        while(!q.isEmpty()) {
            spfa_P i = q.poll();
            s.remove(i.a);
            for(spfa_P nei : adjList.get(i.a)) {
                int d = i.b + nei.b;
                if(d < dist[nei.a]) {
                    dist[nei.a] = d;
                    par[nei.a] = i.a;
                    if(!s.contains(nei.a)) {
                        q.offer(new spfa_P(nei.a, dist[nei.a]));
                    }
                }
            }
        }
        return new int[][] {dist, par};
    }

    static class spfa_P {
        int a, b;

        spfa_P(int a_, int b_) {
            a = a_;
            b = b_;
        }

        @Override
        public String toString() {
            return "Pair{" + "a = " + a + ", b = " + b + '}';
        }

        public boolean equalsSafe(Object o) {
            if(this == o) return true;
            if(o == null || getClass() != o.getClass()) return false;
            spfa_P p = (spfa_P)o;
            return a == p.a && b == p.b;
        }

        public boolean equalsUnchecked(Object o) {
            spfa_P p = (spfa_P)o;
            return a == p.a && b == p.b;
        }

        @Override
        public boolean equals(Object o) {
            return equalsUnchecked(o);
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b);
        }
    }

    // dijk_P = {node, dist}
    static int[][] dijk(int src, List<List<dijk_P>> adjList) {
        return dijk(src, adjList, IBIG);
    }


    static int[][] dijk(int src, List<List<dijk_P>> adjList, int inf) {
        int n = adjList.size(), dist[] = new int[n], par[] = new int[n];
        fill(dist, inf);
        fill(par, -1);
        dist[src] = 0;
        PriorityQueue<dijk_P> q = new PriorityQueue<>((a, b) -> a.b == b.b ? a.a - b.a : b.b - a.b);
        q.offer(new dijk_P(src, 0));
        while(!q.isEmpty()) {
            dijk_P i = q.poll();
            if(i.b > dist[i.a]) {
                continue;
            }
            for(dijk_P nei : adjList.get(i.a)) {
                int d = i.b + nei.b;
                if(d < dist[nei.a]) {
                    dist[nei.a] = d;
                    par[nei.a] = i.a;
                    q.offer(new dijk_P(nei.a, dist[nei.a]));
                }
            }
        }
        return new int[][] {dist, par};
    }

    static class dijk_P {
        int a, b;

        dijk_P(int a_, int b_) {
            a = a_;
            b = b_;
        }

        @Override
        public String toString() {
            return "Pair{" + "a = " + a + ", b = " + b + '}';
        }

        public boolean equalsSafe(Object o) {
            if(this == o) return true;
            if(o == null || getClass() != o.getClass()) return false;
            dijk_P p = (dijk_P)o;
            return a == p.a && b == p.b;
        }

        public boolean equalsUnchecked(Object o) {
            dijk_P p = (dijk_P)o;
            return a == p.a && b == p.b;
        }

        @Override
        public boolean equals(Object o) {
            return equalsUnchecked(o);
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b);
        }
    }

    static int get(P e, int v) {
        return e.a == v ? e.b : e.a;
    }

    static class P {
        int a, b, c;

        P(int a_, int b_, int c_) {
            a = a_;
            b = b_;
            c = c_;
        }

        @Override
        public String toString() {
            return "Pair{" + "a = " + a + ", b = " + b + '}';
        }

        public boolean equalsSafe(Object o) {
            if(this == o) return true;
            if(o == null || getClass() != o.getClass()) return false;
            P p = (P)o;
            return a == p.a && b == p.b;
        }

        public boolean equalsUnchecked(Object o) {
            P p = (P)o;
            return min(a, b) == min(p.a, p.b) && max(a, b) == max(p.a, p.b);
        }

        @Override
        public boolean equals(Object o) {
            return equalsUnchecked(o);
        }

        @Override
        public int hashCode() {
            return Objects.hash(min(a, b), max(a, b));
        }
    }

    static BufferedReader __in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter __out = new PrintWriter(new OutputStreamWriter(System.out));
    static StringTokenizer input;
    static Random rand = new Random();

    // references
    // IBIG = 1e9 + 7
    // IRAND ~= 3e8
    // IMAX ~= 2e10
    // LMAX ~= 9e18
    // constants
    static final int IBIG = 1000000007;
    static final int IRAND = 327859546;
    static final int IMAX = 2147483647;
    static final int IMIN = -2147483648;
    static final long LMAX = 9223372036854775807L;
    static final long LMIN = -9223372036854775808L;
    // util
    static int minof(int a, int b, int c) {return min(a, min(b, c));}
    static int minof(int... x) {if(x.length == 1) return x[0]; if(x.length == 2) return min(x[0], x[1]); if(x.length == 3) return min(x[0], min(x[1], x[2])); int min = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] < min) min = x[i]; return min;}
    static long minof(long a, long b, long c) {return min(a, min(b, c));}
    static long minof(long... x) {if(x.length == 1) return x[0]; if(x.length == 2) return min(x[0], x[1]); if(x.length == 3) return min(x[0], min(x[1], x[2])); long min = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] < min) min = x[i]; return min;}
    static int maxof(int a, int b, int c) {return max(a, max(b, c));}
    static int maxof(int... x) {if(x.length == 1) return x[0]; if(x.length == 2) return max(x[0], x[1]); if(x.length == 3) return max(x[0], max(x[1], x[2])); int max = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] > max) max = x[i]; return max;}
    static long maxof(long a, long b, long c) {return max(a, max(b, c));}
    static long maxof(long... x) {if(x.length == 1) return x[0]; if(x.length == 2) return max(x[0], x[1]); if(x.length == 3) return max(x[0], max(x[1], x[2])); long max = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] > max) max = x[i]; return max;}
    static int powi(int a, int b) {if(a == 0) return 0; int ans = 1; while(b > 0) {if((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static long powl(long a, int b) {if(a == 0) return 0; long ans = 1; while(b > 0) {if((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static int floori(double d) {return (int)d;}
    static int ceili(double d) {return (int)ceil(d);}
    static long floorl(double d) {return (long)d;}
    static long ceill(double d) {return (long)ceil(d);}
    static void shuffle(int[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); int swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(long[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); long swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(double[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); double swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static <T> void shuffle(T[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); T swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void rsort(int[] a) {shuffle(a); sort(a);}
    static void rsort(long[] a) {shuffle(a); sort(a);}
    static void rsort(double[] a) {shuffle(a); sort(a);}
    static int randInt(int min, int max) {return rand.nextInt(max - min + 1) + min;}
    // input
    static void r() throws IOException {input = new StringTokenizer(__in.readLine());}
    static int ri() throws IOException {return Integer.parseInt(__in.readLine());}
    static long rl() throws IOException {return Long.parseLong(__in.readLine());}
    static int[] ria(int n) throws IOException {int[] a = new int[n]; input = new StringTokenizer(__in.readLine()); for(int i = 0; i < n; ++i) a[i] = Integer.parseInt(input.nextToken()); return a;}
    static long[] rla(int n) throws IOException {long[] a = new long[n]; input = new StringTokenizer(__in.readLine()); for(int i = 0; i < n; ++i) a[i] = Long.parseLong(input.nextToken()); return a;}
    static char[] rcha() throws IOException {return __in.readLine().toCharArray();}
    static String rline() throws IOException {return __in.readLine();}
    static int rni() throws IOException {input = new StringTokenizer(__in.readLine()); return Integer.parseInt(input.nextToken());}
    static int ni() {return Integer.parseInt(input.nextToken());}
    static long rnl() throws IOException {input = new StringTokenizer(__in.readLine()); return Long.parseLong(input.nextToken());}
    static long nl() {return Long.parseLong(input.nextToken());}
    // output
    static void pr(int i) {__out.print(i);}
    static void prln(int i) {__out.println(i);}
    static void pr(long l) {__out.print(l);}
    static void prln(long l) {__out.println(l);}
    static void pr(double d) {__out.print(d);}
    static void prln(double d) {__out.println(d);}
    static void pr(char c) {__out.print(c);}
    static void prln(char c) {__out.println(c);}
    static void pr(char[] s) {__out.print(new String(s));}
    static void prln(char[] s) {__out.println(new String(s));}
    static void pr(String s) {__out.print(s);}
    static void prln(String s) {__out.println(s);}
    static void pr(Object o) {__out.print(o);}
    static void prln(Object o) {__out.println(o);}
    static void prln() {__out.println();}
    static void pryes() {__out.println("yes");}
    static void pry() {__out.println("Yes");}
    static void prY() {__out.println("YES");}
    static void prno() {__out.println("no");}
    static void prn() {__out.println("No");}
    static void prN() {__out.println("NO");}
    static void pryesno(boolean b) {__out.println(b ? "yes" : "no");};
    static void pryn(boolean b) {__out.println(b ? "Yes" : "No");}
    static void prYN(boolean b) {__out.println(b ? "YES" : "NO");}
    static void prln(int... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), ++i); __out.println(a[a.length - 1]);}
    static void prln(long... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), ++i); __out.println(a[a.length - 1]);}
    static <T> void prln(Collection<T> c) {int n = c.size() - 1; Iterator<T> iter = c.iterator(); for(int i = 0; i < n; __out.print(iter.next()), __out.print(' '), ++i); if(n >= 0) __out.println(iter.next());}
    static void h() {__out.println("hlfd");}
    static void flush() {__out.flush();}
    static void close() {__out.close();}
}