#include<bits/stdc++.h>
#pragma G++ optimize(1,2,3,"Ofast","inline","-fgcse","-fgcse-lm","-fipa-sra","-ftree-pre","-ftree-vrp","-fpeephole2","-ffast-math","-fsched-spec","unroll-loops","-falign-jumps","-falign-loops","-falign-labels","-fdevirtualize","-fcaller-saves","-fcrossjumping","-fthread-jumps","-funroll-loops","-fwhole-program","-freorder-blocks","-fschedule-insns","inline-functions","-ftree-tail-merge","-fschedule-insns2","-fstrict-aliasing","-fstrict-overflow","-falign-functions","-fcse-skip-blocks","-fcse-follow-jumps","-fsched-interblock","-fpartial-inlining","no-stack-protector","-freorder-functions","-findirect-inlining","-fhoist-adjacent-loads","-frerun-cse-after-loop","inline-small-functions","-finline-small-functions","-ftree-switch-conversion","-foptimize-sibling-calls","-fexpensive-optimizations","-funsafe-loop-optimizations","inline-functions-called-once","-fdelete-null-pointer-checks")
using namespace std;

#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1000000,stdin)), p1==p2 ? EOF : *p1++)
char buf[1000000], *p1 = buf, *p2 = buf;
inline const void read(int &a){ register char ch=getchar();bool f=false;a=0;while(ch<'0'||ch>'9')ch=='-'&&(f=true),ch=getchar();while(ch<='9'&&ch>='0')a=(a<<1)+(a<<3)+(ch^48),ch=getchar();f&&(a=-a); }

vector <pair<int,int> >mp[100010];

int d[100200];
bool vis[100200];
int n,m,k,s;
list <int>q;
bool cmp(int a,int b)
{
    return d[a]<d[b];
}
int main()
{
	srand(time(0));
	read(n),read(m),read(s);
	int v,x,y,z;
    for(register int i = 1;i <= m; ++i) {
        read(x),read(y),read(z); 
        mp[x].push_back(make_pair(y,z));
    }
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	vis[s]=1;
	q.push_back(s);
	for(;!q.empty();)
	{
		if(rand()%((q.size()>>2+1>>3)+1)==0)
		{
			q.sort(cmp);
		}
		int x=q.front();
		q.pop_front();
        vis[x]=0;
		for(register int i=0;i<mp[x].size();i++)
		{
			int p=mp[x][i].first;
			int lp=mp[x][i].second;
			if(d[x]+lp<d[p])
			{
				d[p]=d[x]+lp;
				if(!vis[p]) 
				{
					if(d[p]>d[q.front()])q.push_back(p);
					else q.push_front(p);
					vis[p]=1;
				}
			}
		}
	}
	for(register int i=1;i<=n;i++)
	{
	    cout<<d[i]<<' ';
	}
	return 0;
}

80分大佬帮帮忙