#include <bits/stdc++.h>
#define INF 2147483647
using namespace std;

struct Node { int id, cost; };
vector<Node> nodes[100100];
int n, m, s, a, b, c, dis[100010], vis[100010];

int dijkstra(int start) {
    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[start] = 0;
    for (int i = 1; i <= n; i++) {
        int mn = 0, vl = INF;
        for (int j = 1; j <= n; j++) if (!vis[j] && dis[j] <= vl) vl = dis[j], mn = j;
        vis[mn] = true;
        for (auto node : nodes[mn]) {
            int id = node.id, cost = node.cost;
            if (dis[id] > dis[mn] + cost) dis[id] = dis[mn] + cost;
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m && scanf("%d%d%d", &a, &b, &c); i++) nodes[a].push_back({b, c});
    dijkstra(s);
    for (int i = 1; i <= n; i++) printf("%d ", dis[i]);
    return 0;
}