#include<bits/stdc++.h>
using namespace std;
struct node{
	int v,w;
};
vector<node> e[5005];
long long n,m,s,x,y,w,d[5005],f[5005][5005];
bool b[5005];
int main() {
	cin>>n>>m>>s;
	for(int i=1; i<=n; i++) {
		for(int j=1;j<=n;j++)
		{
			f[i][j]=INT_MAX;
		}
	}
	for(int i=1; i<=m; i++) {
		cin>>x>>y>>w;
		if(x==y) {
			continue;
		}
		if(f[x][y]>w) {
			f[x][y]=w;
		}
	}
	//memset(d,0x3f3f3f3f,sizeof(d));
	for(int i=1; i<=n; i++) {
		d[i]=INT_MAX;
	}
	for(int i=1; i<=n; i++) {
		d[i]=f[s][i];
	}
	d[s]=0;
	memset(b,false,sizeof(b));
	b[s]=true;
	for(int i=1; i<=n; i++) {
		int mind=INT_MAX,k=0;
		for(int j=1; j<=n; j++) {
			if((!b[j])&&(d[j]<mind)) {
				mind=d[j];
				k=j;
			}
		}
		if(k==0)	break;
		b[k]=true;
		for (auto ed : e[k]) {
            int v = ed.v, w = ed.w; 
            if (d[v] > d[k] + w) {
                d[v] = d[k] + w;
            }
        }
	}
	for(int i=1; i<=n; i++) {
		cout<<d[i]<<" ";
	}
	return 0;
}