rt

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii; 
const int N=1e5+5,M=5e5+5;
int n,m,s;
vector<pii>g[N]; 
int dis[N];
int cnt[N],sum;
bool vis[N]; 
void SPFA()
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    deque<int>q;//双端队列 
    q.push_back(s);
    vis[s]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        vis[u]=false;
    	for(pii i:g[u]) 
        {
            int v=i.first,w=i.second;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    vis[v]=true;
                    cnt[v]++;
                    if(2<=cnt[v]&&cnt[v]<=sqrt(n))//mrsz优化 
						q.push_front(v);
                    if(!q.empty()&&dis[v]>dis[q.front()]+sqrt(sum))//SLF带容错
                	    q.push_front(v);
                	else
                		q.push_back(v);
                }
            }
        }
    }
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back({v,w});
		sum+=w;
	}
	SPFA();
	for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
	return 0;
}