#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,m,dis[300001],ans[300001];
bool vis[600001];
vector<pair<int,int>> v[600001];
deque<int> q;
inline int read()
{
	int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
        putchar(x%10+'0');
        return;
    }
    putchar(x+'0');
}
signed main()
{
	n=read(),m=read();
	int s=read();
	for(int i=1;i<=m;++i)
	{
		int a=read(),b=read(),c=read();
		v[a].push_back({b,c});
	}
		for(int i=1;i<=n;++i) dis[i]=2147483647;
		for(int i=1;i<=n;++i) vis[i]=0;
		q.push_back(s);
		vis[s]=1;
		int cnt=1,sum=0;
		dis[s]=0;
		while(!q.empty())
		{
//			for(int i=0;i<q.size();i++) cout<<q[i]<<" ";
//			cout<<endl;
//			cout<<endl;
			int nw=q.front();
        	q.pop_front();
        	cnt--;
        	sum-=dis[nw];
        	if(!q.empty()&&dis[q.front()]>dis[q.back()]) swap(q.front(),q.back());
        	vis[nw]=0;
        	while(cnt*dis[nw]>sum)
        	{
        		q.push_back(nw);
            	nw=q.front();
            	q.pop_front();
//            	cout<<"f";
        	}
        	for(int i=0;i<v[nw].size();++i)
        	{
        		int y=v[nw][i].first,z=v[nw][i].second;
        		if(dis[y]>dis[nw]+z)
        		{
//        			cout<<y<<" "<<vis[y]<<endl;
        			dis[y]=dis[nw]+z;
        			if(!vis[y])
        			{
        				if(!q.empty())
        				{
        					if(dis[y]<=dis[q.front()])
        					{
//        						cout<<y<<1<<endl;
        						q.push_front(y);
							}else
							{
//								cout<<y<<endl;
								q.push_back(y);
							}
							if(dis[q.front()]>dis[q.back()]) swap(q.front(),q.back());
						}else q.push_back(y);
						vis[y]=1;
						sum+=dis[y];
						cnt++;
					}
//					cout<<endl;
				}
			}
		}
	for(int i=1;i<=n;++i) write(dis[i]),putchar(' ');
	return 0;
}

LLL和SLF+swap优化的SPFA，60pts。