#include<bits/stdc++.h>
using namespace std;
int h[100001],nxt[500001],val[500001],zd[500001],cnt=0;
int n,m,s,dis[100001];
bool inq[100001];
int f,e;
void addedge(int a,int b,int c){
	cnt++;
	val[cnt]=c,zd[cnt]=b,nxt[cnt]=0;
	nxt[cnt]=h[a];
	h[a]=cnt;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;
	for(register int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	memset(dis,-1,sizeof(dis));
	dis[s]=0;
	while(1){
		int q=-1,u=-1;
		for(register int i=1;i<=n;i++)if(!inq[i]&&dis[i]!=-1&&(q==-1||q>dis[i]))q=dis[i],u=i;
		if(q==-1)break;
		inq[u]=1;
		for(register int p=h[u];p;p=nxt[p]){
			int v=zd[p],c=val[p];
			if(inq[v]==0&&(dis[v]==-1||dis[v]>dis[u]+c))dis[v]=dis[u]+c; 
		}
	}
	for(register int i=1;i<=n;i++)
		cout<<dis[i]<<" ";
}