#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int INF=0x3f3f3f3f;
priority_queue<int>que;
struct node{
	int vv,ww;
};
struct edge{
	int w,to,nxt;
}e[N];
int n,m,st,dis[N],cnt,head[N];
bool vis[N];
void add(int u,int v,int d){
    cnt++;
    e[cnt].w=d;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dijkstra(int st){
	que.push({st});
	vis[st]=1;
	dis[st]=0;
	while(!que.empty()){
		int u=que.top();
		que.pop(); 
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,w=e[i].w; 
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				vis[v]=1;
				que.push({v});
			}
		}
	}
}
int main(){
	cin>>n>>m>>st;
	for(int i=1;i<=n;i++)dis[i]=INF;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra(st);
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}

TLE祭录