#include <stdio.h>
#include <limits.h>

#define MAX 20

int main() {
    int n, e;
    scanf("%d", &n);

    // Only invalid test cases
    if (n < 0) {
        printf("Invalid input");
        return 0;
    }

    scanf("%d", &e);

    int graph[MAX][MAX] = {0};
    int dist[MAX];
    int visited[MAX] = {0};

    for (int i = 0; i < e; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        graph[u][v] = w;
    }

    int source;
    scanf("%d", &source);

    for (int i = 0; i < n; i++)
        dist[i] = INT_MAX;

    dist[source] = 0;

    for (int i = 0; i < n - 1; i++) {
        int min = INT_MAX, u = -1;

        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }

        if (u == -1) break;

        visited[u] = 1;

        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0 &&
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // STRICT OUTPUT
    for (int i = 0; i < n; i++) {
        printf("%d%t%d\n", i, dist[i]);
    }

    return 0;
}