#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int> > e[10005];
long long dist[10005],vis[10005];
long long MAXN=pow(2,31)-1;
long long n,m,s;

void dijkstra(int begin){
	memset(dist,0x3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	dist[begin]=0;
	for(int k=1;k<n;k++){
		int u=0;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dist[i]<dist[u])u=i;
		}
		if(u==0)return;
		vis[u]=1;
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].first,c=e[u][i].second;
			if(!vis[v]&&dist[v]>dist[u]+c)dist[v]=dist[u]+c;
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
        cin>>u>>v>>w;
        pair<int,int> p1(v,w);
        e[u].push_back(p1);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		if(dist[i]==0x3f)cout<<pow(2,31)-1<<" ";
		
		else cout<<dist[i]<<" ";
	}
	return 0;
}