rt

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,m,s;
int dis[N],to[N],w[N],nxt[N],head[N],k;
bool vis[N];
void add(int x,int y,int val) {
	to[k]=y;
	w[k]=val;
	nxt[k]=head[x];
	head[x]=k++;
}
void dijkstra() {
	memset(dis,0x3f,sizeof dis);
//	memset(vis,0,sizeof vis);
	memset(head,-1,sizeof head);
	dis[s]=0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	q.push({0,s});
	while(!q.empty()) {
		pair<int,int> t=q.top();
		q.pop();
		int v=t.second,cnt=t.first;
		if(vis[v]) continue;
		vis[v]=true;
		for(int i=head[v]; ~i; i=nxt[i]) {
			if(dis[to[i]]>cnt+w[i]) {
				dis[to[i]]=cnt+w[i];
				q.push({dis[to[i]],to[i]});
			}
		}
	}
}
signed main() {
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1; i<=m; i++) {
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dijkstra();
	for(int i=1; i<=n; i++)
		cout<<dis[i]<<" ";
	return 0;
}