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.*;
import static java.util.Arrays.fill;

public class RocketMines {
    private final List<Road>[] roads;
    private final int capital;
    private final int n;

    public RocketMines(final int n, final int capital) {
        this.capital = capital;
        this.n = n;
        roads = new List[n];
    }

    public void addRoad(final int city1, final int city2, final int length) {
        insertRoad(city1, city2, length);
        insertRoad(city2, city1, length);
    }

    private void insertRoad(final int from, final int to, final int length) {
        if (roads[from] == null) {
            roads[from] = new ArrayList<Road>();
        }
        roads[from].add(new Road(to, length));
    }

    public int dijkstra(final int goal) {
        int[] distances = new int[n];
        fill(distances, Integer.MAX_VALUE);
        distances[capital] = 0;

        Queue<QueueItem> queue = new PriorityQueue<QueueItem>();
        queue.add(new QueueItem(0, capital));
        while (!queue.isEmpty()) {
            QueueItem cur = queue.poll();
            int dist = distances[cur.city];
            if (dist < cur.knowningDist) {
                continue;
            }
            for (Road r : roads[cur.city]) {
                int v = r.to;
                int currDist = dist + r.length;
                if (distances[v] > currDist) {
                    distances[v] = currDist;
                    queue.add(new QueueItem(currDist, v));
                }
            }
        }

        Set<MineOnRoad> minesOnRoad = new HashSet<MineOnRoad>();
        for (int i = 0; i < n; i++) {
            int dist = distances[i];
            for (Road r : roads[i]) {
                int toDist = dist + r.length;
                if (toDist > goal && goal > dist && distances[r.to] + r.length + dist >= 2 * goal) {
                    minesOnRoad.add(new MineOnRoad(i, r.to, goal - dist, toDist - goal));
                }  
            }
        }
        
        int minesInCity = 0;
        for (int dist: distances) {
            if (dist == goal) {
                minesInCity++;
            }
        }
        return minesInCity + minesOnRoad.size();
    }

    private class MineOnRoad {
        private final int city1, city2;
        private final int length1, length2;

        private MineOnRoad(final int city1, final int city2, final int length1, final int length2) {
            if (city1 < city2) {
                this.city1 = city1;
                this.city2 = city2;
                this.length1 = length1;
                this.length2 = length2;
            } else {
                this.city1 = city2;
                this.city2 = city1;
                this.length1 = length2;
                this.length2 = length1;
            }
        }

        @Override
        public int hashCode() {
            int hash = city1;
            hash = 31 * hash + city2;
            hash = 31 * hash + length1;
            hash = 31 * hash + length2;
            return hash;
        }

        @Override
        public boolean equals(Object o) {
            if (o == null || !(o instanceof MineOnRoad)) {
                return false;
            }

            MineOnRoad that = (MineOnRoad) o;
            return that.city1 == this.city1 &&
                   that.city2 == this.city2 &&
                   that.length1 == this.length1 &&
                   that.length2 == this.length2;
        }
    }

    private class Road {
        private final int to;
        private final int length;

        public Road(final int to, final int length) {
            this.to = to;
            this.length = length;
        }
    }

    private class QueueItem implements Comparable<QueueItem> {
        private final int knowningDist;
        private final int city;

        public QueueItem(final int knowningDist, final int city) {
            this.knowningDist = knowningDist;
            this.city = city;
        }

        @Override
        public int compareTo(final QueueItem queue) {
            return knowningDist - queue.knowningDist;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int s = scanner.nextInt() - 1;
        RocketMines rocketMines = new RocketMines(n, s);
        for (int i = 0; i < m; i++) {
            rocketMines.addRoad(scanner.nextInt() - 1, scanner.nextInt() - 1, scanner.nextInt());
        }
        System.out.println(rocketMines.dijkstra(scanner.nextInt()));
    }
}