#include <bits/stdc++.h>
#define endl "\n"
#define fr(ii,ss,tt) for(int ii=ss;ii<=tt;ii++)
#define rf(ii,ss,tt) for(int ii=ss;ii>=tt;ii--)
#define pii pair<int,int>
#define pt printf
#define fi first
#define eb emplace_back
#define ll long long
#define se second
using namespace std;
inline void rd() {}
template<typename T, typename... args>inline void rd(T&x, args&...y) {
	char ch;
	bool f = 0;
	for (ch = getchar(); ch < '0' || '9' < ch; ch = getchar())if (ch == '-')f = 1;
	for (x = 0; '0' <= ch && ch <= '9'; ch = getchar())x = (x << 1) + (x << 3) + ch - '0';
	if (f)x = -x;
	rd(y...);
}
const int N = 1e6 + 1, inf = 2e9;
int n, m, s;
vector<pii> eg[N];
static priority_queue<pii, vector<pii>, less<pii>> h;
static bool be[N];
static int dis[N];
void dj() {
    fr(ii,1,n)be[ii] = 0, dis[ii] = inf;
    dis[s] = 0, h.push({dis[s], s});
    while (!h.empty()) {
        int f = h.top().se;
        h.pop();
        if (be[f])continue;
        be[f] = 1;
        for (pii&to : eg[f]) {
            int t = to.fi, v = to.se, nw = dis[f] + v;
            if (dis[t] > nw) {
                dis[t] = nw;
                h.push({dis[t], t});
            }
        }
    }
    fr(ii,1,n) {
        pt("%d ", dis[ii]);
    }
}
int main() {
    rd(n, m, s);
    fr(ii,1,m) {
        int a, b, v;
        rd(a, b, v);
        eg[a].eb(b, v);
    }
    dj();
    return 0;
}