#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

#define N 100000

struct Node {
    int idx;
    int weight;
};

bool visited[N];
int dist[N];

int n, m;
vector<Node> adj_list[N];

void init_dist(int max_node) {
    for (int i = 1; i <= max_node; i++)
        dist[i] = INT_MAX;
}

void init_visited(int max_node) {
    for (int i = 1; i <= max_node; i++)
        visited[i] = false;
}

void dijkstra(int start_node) {

    init_dist(n);
    init_visited(n);
    
    dist[start_node] = 0;

    // iterate through all vertices to find shortest path for all of them
    for (int v_idx = 1; v_idx <= n - 1; v_idx++) {

        int mindist_idx = -1;
        // current minimum distance from src to mindist_idx;
        int mindist = INT_MAX;
        
        // find node with the shortest distance from src that
        // was not visited
        for (int v = 1; v <= n; v++) {
            if (visited[v] == false && dist[v] <= mindist) {
                mindist_idx = v;
                mindist = dist[v];
            }
        }

        visited[mindist_idx] = true;

        // update all nodes distances of the adjacent vertices of the
        // found vertex
        for (Node adj_node : adj_list[mindist_idx]) {
            if (!visited[adj_node.idx] && dist[mindist_idx] != INT_MAX
                && dist[mindist_idx] + adj_node.weight < dist[adj_node.idx]) {

                    dist[adj_node.idx] = dist[mindist_idx] + adj_node.weight;
                }
        }
    }
}

int main() {

    int s, x, y, c;

    scanf("%d %d %d", &n, &m, &s);

    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &x, &y, &c);
        adj_list[x].push_back({y, c});
    }

    dijkstra(s);

    for (int i = 1; i <= n; i++) {
        if (dist[i] != INT_MAX)
            printf("%d ", dist[i]);
        else printf("NaN ");
    }

    printf("\n");

    return 0;
}