#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define lowbit(x) (x & ( -x ))
//#define i64 __int64
//typedef __int64 i64;
#define PII pair<ll,ll>
#define VCT vector 
typedef long long ll;
typedef unsigned long long ull;
const ll N = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;
ll a[N], summ[N], v[N], fa[N], in[N], b[N], num[N];
ll n, m, d, h, x, y, z, k, pre, cnt, res, len, tot, ans, sum, now, maxn = -1e18, minn = 1e18;
priority_queue <ll, vector<ll>, greater<ll> > pq;	//less 降序排列 优先队列
priority_queue <ll, vector<ll>, less<ll> > pq1;		//默认升序
string s, s1, s2, s3;
char ss[1000][1000];
VCT <ll> vis[N], vis1;
map <ll, ll> mp;
unordered_map <ll, ll> mpp, mp2;
PII pi[N];
bool ok[N];
ull qpow(ull a, ull n) {
	ull ans = 1;
	while (n) {
		if (n & 1)
			ans = (ans * a) % mod;
		a = (a * a) % mod;
		n >>= 1LL;
	}
	return ans;
}
 //快速幂
set <ll> PrimeZ(ll x) {
	set <ll> primeZ;
	for (int i = 2; i <= sqrt(x); i++) {
		if (x % i)	continue;
		primeZ.insert(i);
		while (x % i == 0)	x /= i;
	}
	if (x > 1)	primeZ.insert(x);
	return primeZ;
}
//分解质因数
ll ls(ll p) { return p << 1; }
ll rs(ll p) { return p << 1 | 1; }
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

void solve()
{
	cin >> n >> m >> cnt;
	map <PII, ll> mp;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y >> pre;
		vis[x].push_back(y);
		mp[{x, y}] = pre;
	}
	priority_queue <PII> p;
	p.push({ 0,cnt });
	for (int i = 0; i <= n; i++)	b[i] = INF;
	b[cnt] = 0;
	while (p.size()) {
		k = p.top().second;
		p.pop();
		if (ok[k])	continue;
		ok[k] = 1;
		for (auto i : vis[k]) {
			if (b[i] > b[k] + mp[{k, i}]) {
				b[i] = b[k] + mp[{k, i}];
				p.push({ -b[i],i });
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << b[i] << ' ';
	}
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); std::cout.tie(0);
	//int t; cin >> t;
	//while (t--)
		solve();
	return 0;
}
/*



*/