#include<bits/stdc++.h>
using namespace std;
int n,m,s,u,v,w;
long long int dis[100001];
struct node{
	int v,w;
	node(int _v=0,int _w=0):v(_v),w(_w){}
	bool operator<(node const&a)const{
		return w>a.w;
	}
};
vector<node>edge[10010];
bool vis[100001];
void Dijkstra();
priority_queue<node>que;
int main(){
	cin>>n>>m>>s;
	for(int i=0;i<m;i++){
		cin>>u>>v>>w;
		edge[u].push_back(node(v,w));
		edge[v].push_back(node(u,w));
	}
	memset(dis,0x3f,sizeof(dis));
	Dijkstra();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
} 
void Dijkstra(){
	dis[s]=0;
	que.push(node(s,0));
	for(int i=1;i<=n;i++){
		u=que.top().v;que.pop();
		vis[u]=true;
		for(int j=1;j<=edge[u].size();j++){
			int v=edge[u][j].v,w=edge[u][j].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				que.push(node(v,dis[v]));
			}
		}
		while(!que.empty()&&vis[que.top().v])que.pop();
	}
}