#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int N = 2e6 + 10;

typedef pair<int, int > pr;

int h[N], ne[N], e[N], w[N];
int d[N];
bool st[N];
int idx = 1;
void add(int a, int b, int  c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int n, m;
int start;

void dij() {
	d[start] = 0;

	priority_queue<pr, vector<pr>, greater<pr>> q;

	q.push({ start,0 });

	while (!q.empty()) {
		auto t = q.top();
		q.pop();
		int ver = t.first;
		if (st[ver]) continue;
		st[ver] = true;
		for (int i = h[ver]; i != 0; i = ne[i]) {
			int j = e[i];
			if (d[j] > t.second + w[i]) {
				d[j] = t.second+ w[i];
				q.push({ j,d[j] });
			}
		}
		
	}


}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	///memset(h, - 1, sizeof h);
	memset(d, 0x3f, sizeof d);
	
	scanf("%d%d%d", &n, &m,&start);
	while (m--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		
		//cout << m << "\n";
		add(a, b, c);
	}

	dij();
	if (d[n] != 0x3f3f3f3f) for (int i = 1; i <= n; i++) cout << d[i] << " ";
	else
	{
		cout << "2147483647" << "\n";
	}

}