/*
 * N log N
 */

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const long MAX = 50010;

struct muchie {long x,c; muchie *n;};
class nod {
	public : 
	muchie *a;
	nod() {
		a = 0;
	}
	void add(long x, long y) {
		muchie *tmp = new muchie;
		tmp -> x = x; tmp -> c = y;
		tmp -> n = a;
		a = tmp;
		return ;
	}
} G[MAX];

inline long min (long x, long y) { return (x<y)?x:y; }

long n, m, s;
long D[MAX];
bool U[MAX];

struct comp {
	bool operator()(long x, long y) {
		return D[x] > D[y];
	}
};
priority_queue<long, vector<long>, comp> Q;

void dijkstra(long source) { 
	memset(D, 0x3f, sizeof(D));
	D[source] = 0;U[source] = true;
	Q.push(source);
	while ( 1 ) {
		if ( Q.empty() ) break;
		long x = Q.top(); Q.pop();
		fprintf(stderr, "-- %ld\n", x);
		for (muchie *p=G[x].a; p; p=p->n) 
			if ( D[p->x] > D[x]+p->c ) {
				D[p->x] = D[x] + p->c;
				if ( !U[p->x] ) {
					Q.push(p->x);
					U[p->x] = true;
				}
			}
		
	}
}

int main() {
	long i;

	freopen("dijkstra.in", "r", stdin);
	scanf("%ld %ld %ld", &n, &m, &s);
	for (i=0; i<m; ++i) {
		long x,y,c;
		scanf("%ld %ld %ld", &x, &y, &c);
		G[x].add(y,c);
	}
	fclose(stdin);

	dijkstra(s);
	freopen("dijkstra.out", "w", stdout);
	for (i=1; i<=n; ++i) 
		if ( D[i]<0x3f3f3f3f ) 
			printf("%ld ", D[i]);
		else
			printf("0 ");
	printf("\n");
	return 0;
}