#include<iostream>
#include<vector>
#include<cstring>
using namespace std; 
struct node{
	int to,val;
}temp;
vector<node>gra[10010];
int dis[10000],n,m,s,inf=2147483647;
bool vis[10000];
void dijkstra()
{
	memset(dis,inf,sizeof(dis));
	dis[s]=0;
	vis[s]=1;
	for(int p=1;p<=n;p++)
	{
		int k=s,min=inf;
		for(int i=1;i<=n;i++)
			if((k==s||dis[i]<dis[k])&&!vis[i])
				k=i,min=dis[i];
		vis[k]=1;
		for(int i=0;i<gra[k].size();i++)
		{
			int v=gra[k][i].val;
			if(!vis[i]&&min+v<dis[gra[k][i].to])
				dis[gra[k][i].to]=v+min;
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int p=1,x;p<=m;p++)
		cin>>x>>temp.to>>temp.val,gra[x].push_back(temp);
	dijkstra();
	for(int p=1;p<=n;p++)
		cout<<dis[p]<<' ';
}