RT,32pts

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

#define int long long

const int N = 1400100;

using namespace std;

int n, m, s, jud;

int dist[N];

int h[N], ne[N], to[N], e[N], idx;

bool st[N];

queue <int> q;


int qpow(int a, int n)
{
	int ans = 1;
	while (n)
	{
		if(n & 1) ans *= a;
		n >>= 1;
		a *= a;
	}
	return ans;
}

void add(int a, int b, int w)

{
    to[idx] = b;
    e[idx] = w;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void spfa()

{
    memset(dist, 0x3f, sizeof dist);
    jud = dist[0];
    dist[s] = 0;
    q.push(s);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int b = to[i];
            if (dist[b] > dist[t] + e[i])
            {
                dist[b] = dist[t] + e[i];
                if (!st[b])
                {
                    st[b] = true;
                    q.push(b);
                }
            }
        }
    }
    //if (dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
    //else cout << dist[n] << endl;
}

signed main()

{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	
    memset(h, -1, sizeof h);	
    cin >> n >> m >> s;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
        //add(b, a, w);
    }
    spfa();
    for (int i = 1; i <= n; i ++ )
    {
    	if (dist[i] == jud) cout << qpow(2, 31) - 1 << " ";
    	else cout << dist[i] << " ";
	}
}