#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int a[1010][1010],d[100010],v[100010],n,m,s,x,y,z,u,maxn;
queue<int> q;
int main()
{
	cin>>n>>m>>s;
	memset(a,0x3f,sizeof(a)),memset(d,0x3f,sizeof(d));
	for(int i=1;i<=m;i++) cin>>x>>y>>z,a[x][y]=z;
	q.push(s),d[s]=0,maxn=d[0],v[s]=1;
	while(!q.empty())
	{
		u=q.front(),q.pop(),v[u]=1;
		for(int v=1;v<=n;v++)
		{
			if(a[u][v]<maxn&&d[u]+a[u][v]<d[v])
				d[v]=d[u]+a[u][v],q.push(v); 
		}
	}
	for(int i=1;i<=n;i++) cout<<d[i]<<" ";
	return 0;
}