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

const int N=5e5+7;
LL d[N];//记录用n条边能
struct Edge {
	int to,next,val;
} edge[N];
int head[N];
int cnt=0;
void addedge(int b,int e,int val) {
	cnt++;
	edge[cnt].to=e;
	edge[cnt].next=head[b];
	edge[cnt].val=val;
	head[b]=cnt;
}
int n,m,s;
//dp思路，每一次从上一次做完的继承下来，每n次代表走n次能到点的最大值
LL vis[N];//标记是否入队
LL cnt1[N];//标记每个元素入队次数
bool SPFA(int x) {
	queue<int>q;
	memset(d,0x3f,sizeof(d));
	d[x]=0;
	q.push(x);
	while(!q.empty()) {
		int k=q.front();
		for(int i=head[k]; i; i=edge[i].next) {
			if(d[edge[i].to]>d[k]+edge[i].val) {
		cnt1[edge[i].to]++;
				d[edge[i].to]=d[k]+edge[i].val;
			if(cnt1[edge[i].to]>n-1)return false;
				if(!vis[edge[i].to]) {
					q.push(edge[i].to);
					vis[edge[i].to]=1;
				}
			}
		}
		vis[k]=0;
		q.pop();
	}
}
int main() {

	cin>>n>>m>>s;
	for(int i=1; i<=m; i++) {
		int u,v,w;
		cin>>u>>v>>w;
		addedge(u,v,w);
	}
	SPFA(s);
	for(int i=1; i<=n; i++)
	{
		if(d[i]==0x3f)cout<<pow(2,31)-1;
	    else cout<<d[i]<<" ";	
	}
	return 0;
}