#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

struct vertex
{
    vector<pair<int, int>> adj;
    int dis;
    int id;
    bool known;
};

vertex G[10001];
auto cmp = [](int i, int j){return G[i].dis > G[j].dis;};
priority_queue<int, vector<int>, decltype(cmp)> Q(cmp);

int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++)
        G[i].id = i, G[i].dis = INT_MAX;
    while (m--)
    {
        int v, w, c;
        cin >> v >> w >> c;
        G[v].adj.push_back({w, c});
    }
    G[s].dis = 0; 
    Q.push(s);
    while (!Q.empty())
    {
        int t;
        do
        {
            t = Q.top();
            Q.pop();
        } while(G[t].known && !Q.empty());
        vertex & v = G[t];
        v.known = true;
        int len = v.adj.size();
        for (int i = 0; i < len; i++)
        {
            vertex & w = G[v.adj[i].first];
            if (!w.known)
            {
                int c = v.adj[i].second;
                w.dis = min(w.dis, v.dis + c);
                Q.push(w.id);
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << G[i].dis << ' ';
    return 0;
}