dominator tree

int n,m,root;ll vis[MAX],dist[MAX];vector<pll>v[MAX];vi dag[MAX];vector<plll>edge;int color[MAX];vi topsort,parent[MAX];

int lev[MAX],Sz[MAX];vi dTree[MAX];int table[MAX][50];

void dfs(int s){
    color[s] = 1;
    for(auto it : dag[s]){
        parent[it].pb(s);
        if(!color[it]){
            dfs(it);
        }

    }
    topsort.pb(s);
}

void dij(){
    priority_queue<pll,vector<pll>,greater<pll> >q;
    q.push(pll(0,root));
    for(int i = 0;i<MAX;i++)dist[i] = 1e15;
    dist[root] = 0;
    while(!q.empty()){
        pll x = q.top();
        q.pop();
        if(vis[x.ss])continue;
        vis[x.ss] = 1;
        for(auto it : v[x.ss]){
            if(dist[it.ff]>dist[x.ss]+it.ss){
                dist[it.ff] = dist[x.ss] + it.ss;
                q.push(pll(dist[it.ff],it.ff));
            }
        }
    }

}


void add(int x,int y)
{
    table[x][0] = y;
    lev[x] = lev[y] + 1;
    for(int i = 1;(1<<i)<=n;i++){
        if(table[x][i-1]!=-1){
            table[x][i] = table[table[x][i-1]][i-1];
        }
    }
}

int lca_query(int uu,int vv)
{
    if(lev[vv]<lev[uu])swap(uu,vv);
    int log = 1;
    while((1<<log)<lev[vv])log++;

    for(int i = log;i>=0;i--)
    {
        if(lev[vv] - (1<<i)>=lev[uu])
        {
            vv = table[vv][i];
        }
    }
    if(uu==vv)return uu;

    for(int i = log;i>=0;i--)
    {
        if(table[vv][i]!=-1&&table[vv][i]!=table[uu][i])
        {
            vv = table[vv][i];
            uu = table[uu][i];
        }
    }
    return table[vv][0];
}

void make_dominator_tree(){
     mem(table,-1);
     lev[root] = 1;
     dfs(root);
     reverse(all(topsort));
     for(auto it : topsort){
        if((int)parent[it].size()==0)continue;
        int x = parent[it][0];
        for(int i = 1;i<parent[it].size();i++)x = lca_query(parent[it][i],x);
        dTree[x].pb(it);
        add(it,x);
     }
}

void dfs2(int s,int p = -1){
    Sz[s] = 1;
    for(auto it : dTree[s]){
        if(it==p)continue;
        dfs2(it,s);
        Sz[s]+=Sz[it];
    }
}


int main()
{
    booster()
    ///read("input.txt");

    cin>>n>>m>>root;
    for(int i = 0;i<m;i++){
        ll a,b;ll c;
        cin>>a>>b>>c;
        v[a].pb(pll(b,c));
        v[b].pb(pll(a,c));
        edge.pb(plll(pll(a,b),c));
    }
    dij();

    for(auto it : edge){
        if(dist[it.ff.ff]+it.ss==dist[it.ff.ss]){
            dag[it.ff.ff].pb(it.ff.ss);
        }
        if(dist[it.ff.ss]+it.ss==dist[it.ff.ff]){
            dag[it.ff.ss].pb(it.ff.ff);
        }
    }


    int ans = 0;
    make_dominator_tree();

    dfs2(root);
    for(int i = 1;i<=n;i++)if(i!=root)ans = max(ans,Sz[i]);
    cout<<ans;


    return 0;
}