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

long long n,m,rd[1000000][10] = {0},hd[1000000] = {0},dis[1000000] = {0},type[1000000] = {0},num = 1,t;

void f(int x,int y,int z){
	rd[num][1] = y;
	rd[num][2] = z;
	rd[num][3] = hd[x];
	hd[x] = num;
	num++;
}

void Dijkstra(int s){
	dis[s] = 0;
	for(int i = 1;i<=n;i++){
		int u = 0;
		for(int j = 1;j<=n;j++){
			if(dis[j]<dis[u]&&type[j]==0)	u=j;//找出最小B，放入A 
		}
		type[u] = 1;
		for(int j = hd[u];j!=-1;j = rd[j][3]){ //从最小开始，更新别的最短路 
			int v = rd[j][1];
			if(dis[v]>dis[u] + rd[j][2])	dis[v] = dis[u] + rd[j][2];
		}
	}
}

int main(){
	memset(hd,-1,sizeof(hd));
	memset(dis,0x3f,sizeof(dis));
	cin>>n>>m>>t;
	int x,y,z;
	for(int i = 1;i<=m;i++){
		cin>>x>>y>>z;
		f(x,y,z);
	}
	Dijkstra(t);
	for(int i = 1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
}