#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

int n,m,s;
int ma[10005][10005];
int duan[10005];
bool yes[10005];

int main() {
	cin>>n>>m>>s;
	for(int j=1; j<=m; j++) {
		int x,c,v;
		cin>>x>>c>>v;
		ma[x][c]=v;
	}
	memset(duan,0x3f,sizeof(duan));
	duan[s]=0;
	for(int i=1; i<=n; i++) {
		int mi=-1;
		for(int j=1; j<=n; j++) {
			if(!yes[j]&&(mi==-1||duan[j]<duan[mi])) {
				mi=j;
			}
		}
		yes[mi]=true;
		for(int j=1; j<=n; j++) {
			if(!yes[j]&&ma[i][j]!=0&&duan[mi]+ma[mi][j]<duan[j]) {
				duan[j]=duan[mi]+ma[mi][j];
			}
		}
	}
	for(int i=1; i<=n; i++) {
		if(duan[i]!=0x3f)cout<<duan[i]<<" ";
		else cout<<-2147483647<<" ";
	}
	return 0;
}