#include <bits/stdc++.h>//stupid windows,stupid dev-c++
using namespace std;//I love linux!

int n, m, s;
int vis[114514], dis[114514], inf = 0x7fffffff;
vector<pair<int, int> > photo[114514];

void dijkstra()
{
    int i;
    for (i = 1;i <= n;i++)
    {
        dis[i] = inf;
    }
    dis[s] = 0;
    for (int j = 1;j <= n;j++)
    {
        int temp = inf, k;
        for (int j = 1;j <= n;j++)
        {
            if (!vis[j] && dis[j] < temp)
            {
                temp = dis[j];
                k = j;
            }
        }
        vis[k] = 1;
        for (int j = 0;j < photo[k].size();j++)
        {
            int p = photo[k][j].first;
            int w = photo[k][j].second;
            if (vis[p]) continue;
            if (dis[k] + w < dis[p])
            {
                dis[p] = dis[k] + w;
            }
        }
    }
}

int main()
{
    cin >> n >> m >> s;
    int u, v, w;
    int i;
    for (i = 0;i < m;i++)
    {
        cin >> u >> v >> w;
        photo[u].push_back(make_pair(v, w));
    }
    dijkstra();
    for (i = 1;i <= n;i++)
    {
        cout << dis[i] << " ";
    }
    return 0;
}