#include<bits/stdc++.h>
#define int long long

using namespace std;

const int maxn=1e5+10,maxm=2e5+10;

int a[maxn],cnt=1;

struct node{
	int to=-1;
	int next=-1;
	int c;
}ed[maxm];

void add_edge(int u,int v,int w){
	ed[cnt].to=v;
	ed[cnt].next=a[u];
	a[u]=cnt;
	ed[cnt].c=w;
	cnt++;
}
bool book[maxn];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
int dis[maxn];
signed main(){
	int n,m,s;
	cin>>n>>m>>s;
	cout<<n;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	memset(book,false,sizeof(book));
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	for(int i=1;i<=n;i++) q.push(make_pair(i,dis[i]));
	dis[s]=0;
	q.push(make_pair(s,0));
	while(!q.empty()){
		int s=q.top().first;
		q.pop();
		if(book[s]==true) continue;
		book[s]=true;
		int i=a[s];
		while(ed[i].to!=-1){
			if(dis[s]+ed[i].c<dis[ed[i].to]) dis[ed[i].to]=dis[s]+ed[i].c,q.push(make_pair(ed[i].to,dis[ed[i].to]));
			i=ed[i].next;
		}
	}
	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
	return 0;
}

码风可能有点奇怪，见谅