It's the turn of the year, so Bash wants to send presents to his friends. There are n cities in the Himalayan region and they are connected by m bidirectional roads. Bash is living in city s. Bash has exactly one friend in each of the other cities. Since Bash wants to surprise his friends, he decides to send a Pikachu to each of them. Since there may be some cities which are not reachable from Bash's city, he only sends a Pikachu to those friends who live in a city reachable from his own city. He also wants to send it to them as soon as possible.

He finds out the minimum time for each of his Pikachus to reach its destination city. Since he is a perfectionist, he informs all his friends with the time their gift will reach them. A Pikachu travels at a speed of 1 meters per second. His friends were excited to hear this and would be unhappy if their presents got delayed. Unfortunately Team Rocket is on the loose and they came to know of Bash's plan. They want to maximize the number of friends who are unhappy with Bash.

They do this by destroying exactly one of the other n - 1 cities. This implies that the friend residing in that city dies, so he is unhappy as well.

Note that if a city is destroyed, all the roads directly connected to the city are also destroyed and the Pikachu may be forced to take a longer alternate route.

Please also note that only friends that are waiting for a gift count as unhappy, even if they die.

Since Bash is already a legend, can you help Team Rocket this time and find out the maximum number of Bash's friends who can be made unhappy by destroying exactly one city.

Input

The first line contains three space separated integers n, m and s (2 ≤ n ≤ 2·105, <image>, 1 ≤ s ≤ n) — the number of cities and the number of roads in the Himalayan region and the city Bash lives in.

Each of the next m lines contain three space-separated integers u, v and w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 109) denoting that there exists a road between city u and city v of length w meters.

It is guaranteed that no road connects a city to itself and there are no two roads that connect the same pair of cities.

Output

Print a single integer, the answer to the problem.

Examples

Input

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


Output

2


Input

7 11 2
1 2 5
1 3 5
2 4 2
2 5 2
3 6 3
3 7 3
4 6 2
3 4 2
6 7 3
4 5 7
4 7 7


Output

4

Note

In the first sample, on destroying the city 2, the length of shortest distance between pairs of cities (3, 2) and (3, 4) will change. Hence the answer is 2.
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Random;
import java.util.TreeMap;
import java.util.Vector;







public class Multiplicative {

	/**
	 * @param args
	 */
	static boolean reachable[];
	static Vector<Integer> tree[];
	static int size[];
	static Vector<Integer> weight[];
	static Random r;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InputReader in=new InputReader(System.in);
		OutputWriter out=new OutputWriter(System.out);
		r=new Random();
		int n=in.readInt();int m=in.readInt();int s=in.readInt();
		Vector<Integer> graph[]=new Vector [n+1];
		weight=new Vector[n+1];
		size=new int[n+1];
		//out.printLine(n+" "+m+" "+s);
		
		
		for(int i=0;i<=n;i++){
			graph[i]=new Vector<Integer>();
			weight[i]=new Vector<Integer>();
		}
		
		for(int i=0;i<m;i++){
			int u=in.readInt();
			int v=in.readInt();
			int w=in.readInt();
			//out.printLine(u+" "+v+" "+w);
			weight[u].add(w);
			weight[v].add(w);
			graph[u].add(v);
			graph[v].add(u);
		}
		
		
		
		
		
		Vector<Integer> grr[]=new dijkristras(n, graph, s, weight).getTree() ;
		
	
		for(int i=1;i<=n;i++){
			
			
			for(int j=0;j<grr[i].size();j++){
		//System.out.print(grr[i].get(j)+" ");
			}
		  //  System.out.println("wow");
		}
		
	
denominatortree den=new denominatortree(n, grr,s);
 tree=den.getTree();
	for(int i=1;i<=n;i++){
		
		
		for(int j=0;j<tree[i].size();j++){
	//System.out.print(tree[i].get(j)+" ");
		}
	  //  System.out.println("wow");
	}
	
reachable=new  boolean[n+1];
int max=0;
dfs(s);
for(int i=1;i<=n;i++ ){
	if(i!=s)
	max=Math.max(max, size[i]);
}
out.printLine(max);
out.close();


	}
	/*
	 9 21 5
9 4 1
2 7 5
9 4 5
8 1 4
6 7 3
2 3 3
2 1 2
9 7 5
8 8 4
2 6 1
6 7 1
1 2 1
6 3 2
8 1 4
1 6 4
3 4 4
1 5 1
7 1 5
4 3 2
1 2 5
6 7 1*/
	
 static void dfs(int s){
	size[s]=1;
	reachable[s]=true;
	for(int i=0;i<tree[s].size();i++){
		if(reachable[tree[s].get(i)]==false){
			dfs(tree[s].get(i));
			size[s]=size[s]+size[tree[s].get(i)];
		}
	}
//	System.out.println(size[s]+"asdfadf");
	
}	

}


class dijkristras{
	
	
	
	
	
	Vector<Integer> finalgraph[];
	Vector<Integer>  graph[];
	node1 arr[];
	heapsort hp;
	int arrr[];
	Vector<Integer> reversegraph[];
	long dist[];
	long mm=100000000;
	
	Vector<Integer> w[];
	int n1=0;
	boolean re[];
	public dijkristras(int n,Vector<Integer> grap[],int which,Vector<Integer> w[]) {
		// TODO Auto-generated constructor stub
		finalgraph=new  Vector[n+1];
		reversegraph=new Vector[n+1];
		re=new boolean[n+1];
		for(int i=0;i<=n;i++){
			finalgraph[i]=new Vector<Integer>();
			reversegraph[i]=new Vector<Integer>();
		}
		mm=mm*mm;
		graph=grap;
		this.w=w;
		this.n1=n;
		arr=new node1[n+1];
		 arrr=new int[n+1];
		 dist=new long[n+1];
		 Arrays.fill(dist, mm);
		hp=new heapsort(n);
		for(int i=1;i<=n;i++){
			arr[i]=new node1();
			arrr[i]=hp.len;
			if(i==which){
				arr[i].v=0;
				arrr[1]=hp.len;
			arr[i].ind=i;
				arrr[which]=0;
				hp.add(arr[i]);
				node1 temp=hp.heap[0];
				hp.heap[0]=hp.heap[hp.len-1];
				hp.heap[hp.len-1]=temp;
				dist[i]=0;
				
				
			}
			else{
				arr[i].v=mm;
				arr[i].ind=i;
				arrr[i]=hp.len;
				hp.add(arr[i]);
			}
		
			
		}
	//	System.out.println("yes");
		
		dij();
	makeg();	
		
		
		
		
	}
	
	public Vector<Integer>[] getTree(){
		return finalgraph;
	}
	
	
	void dij(){
		
		while(hp.len!=0){
			node1 nn=hp.extractmin(arrr);
			re[nn.ind]=true;
		//System.out.println(nn.ind+"  hhhh"+" "+dist[nn.ind]);
			for(int i=0;i<graph[nn.ind].size();i++){
			
				if(re[graph[nn.ind].get(i)]==true){
					continue;
				}
				if(dist[graph[nn.ind].get(i)]>dist[nn.ind]+w[nn.ind].get(i)){
                     dist[graph[nn.ind].get(i)]		=		dist[nn.ind]+w[nn.ind].get(i);
                     reversegraph[graph[nn.ind].get(i)]=new Vector <Integer>();
                     reversegraph[graph[nn.ind].get(i)].add(nn.ind);
                   hp.heap[ arrr[ graph[nn.ind].get(i)]].v=	dist[nn.ind]+w[nn.ind].get(i);;
              //	System.out.println(graph[nn.ind].get(i)+" "+arrr[graph[nn.ind].get(i)]+" "+dist[nn.ind]+w[nn.ind].get(i));
                     hp.decreasekey(arrr[graph[nn.ind].get(i)], arrr);
                     
				}
				else if(dist[graph[nn.ind].get(i)]==dist[nn.ind]+w[nn.ind].get(i)){
				    reversegraph[graph[nn.ind].get(i)].add(nn.ind);
				}
			}
			
			
		}
		
		
	}	
	
	void makeg(){
		
		for(int i=1;i<=n1;i++){
		for(int j=0;j<reversegraph[i].size();j++){
			finalgraph[reversegraph[i].get(j)].add(i);
		}	
			
		}
		
	}
	
	
	
	
	
}


class heapsort{
	
	node1 heap[];
	
	int len=0;
	
	public heapsort(int n) {
		// TODO Auto-generated constructor stub
		heap=new node1[n+1];
		
		
		
	}
	
	void add(node1 nrr){
		
		heap[len++]=nrr;
		
	}
	
	
	void decreasekey(int i,int arrr[]){
		
		
		while(i>0){
			
			
			int parent=(i-1)/2;
			if(heap[parent].v>heap[i].v){
				node1 temp=heap[parent];
				heap[parent]=heap[i];
				heap[i]=temp;
				arrr[heap[parent].ind]=parent;
				arrr[heap[i].ind]=i;
				i=parent;
				
				
				
			}
			else{
				break;
			}
		}
		
		
	}
	
	void meanheapify(int i,int arrr[]){
		int l=2*i+1;
		int r=2*i+2;
		int min=i;
		if(l<len&&heap[l].v<heap[min].v){
			min=l;
		}
		if(r<len&&heap[r].v<heap[min].v){
			min=r;
		}
		
		
		
		
		if(min!=i){
			
			
			node1 temp=heap[i];
			heap[i]=heap[min];
			heap[min]=temp;
			arrr[heap[min].ind]=min;
			arrr[heap[i].ind]=i;
			meanheapify(min,arrr);
		}
		
	}
	
	node1 extractmin(int arrr[]){
		node1 temp=heap[0];
		heap[0]=heap[len-1];
	
		len--;
		if(len!=0){
		arrr[heap[0].ind]=0;
	meanheapify(0,arrr);}
		return temp;
		
	}
	
	
	
	
	
}

class node1{
	
	long v,w;
	int ind;
	
}


class  denominatortree {
	Vector<Integer> g[],tree[],rg[],bucket[];
	
	int sdom[],par[],dom[],parent[],label[];
	int rev[],arr[];
	int n;
	int t=0;
	int size[];
	int which;
	public denominatortree(int n,Vector<Integer> graph[],int which) {
		// TODO Auto-generated constructor stub
		g=graph;
		tree=new Vector[n+1];
		rg=new  Vector[n+1];
		bucket=new Vector[n+1];
		
		this.which=which;
		for(int i=0;i<=n;i++){
		
			tree[i]=new Vector<Integer>();
			rg[i]=new Vector<Integer>();
			bucket[i]=new Vector<Integer>();
			
		}
		sdom=new int[n+1];
		par=new int[n+1];
		dom=new int[n+1];
		parent=new int[n+1];
		label=new int[n+1];
		rev=new int[n+1];
		arr=new int[n+1];
		this.n=n;
		size=new int[n+1];
		dfs(which);
		step2();
	}
	
	Vector<Integer>[] getTree(){
		return tree;
	}
	void dfs(int u){
		t++;
		
		arr[u]=t;
	//	System.out.println(" helloo"+" "+u);
		rev[t]=u;
		label[t]=t;
		sdom[t]=t;
		parent[t]=t;
		for(int i=0;i<g[u].size();i++){
		int w=g[u].get(i);
		if(arr[w]==0){
			dfs(w);
			par[arr[w]]=arr[u];
		}
		rg[arr[w]].add(arr[u]);
			
			
		}
		
		
		
	
		
	}
	
	void step2(){
		
		
		for(int i=n;i>=1;i--){
			for(int j=0;j<rg[i].size();j++){
				sdom[i]=Math.min(sdom[i], sdom[find(rg[i].get(j),0)]);
			}
			
			
			if(i>1){bucket[sdom[i]].add(i);}
			
			
			for(int j=0;j<bucket[i].size();j++){
				int w=bucket[i].get(j);
				int v=find(w,0);
				if(sdom[v]==sdom[w]){
					dom[w]=sdom[w];
				}
				else{dom[w]=v;}
			}
			
			
			if(i>1){union(par[i],i);}
			
		}
		
		
for(int i=2;i<=n;i++){
	if(dom[i]!=sdom[i]){
		dom[i]=dom[dom[i]];
	}
	tree[rev[i]].add(rev[dom[i]]);
	tree[rev[dom[i]]].add(rev[i]);
}		
		
	}
	
	int find(int u,int x){
	    if(u==parent[u])return x!=0?-1:u;
	    int v = find(parent[u],x+1);
	    if(v<0)return u;
	    if(sdom[label[parent[u]]]<sdom[label[u]])
	      label[u] = label[parent[u]];
	    parent[u] = v;
	    return x!=0?v:label[u];
	  }
 	void union(int x,int y){
		parent[y]=x;
		
	}
	
	
}

class InputReader {
	 
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public String next() {
		return readString();
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}

	public void flush() {
		writer.flush();
	}

	}

class IOUtils {

	public static int[] readIntArray(InputReader in, int size) {
		int[] array = new int[size];
		for (int i = 0; i < size; i++)
			array[i] = in.readInt();
		return array;
	}

	}
