444

#include <stdio.h>

int main()
{
    int n, m;
    int i[201], j[201], w[201];
    int s;

    scanf("%d%d", &n, &m);
    for (int k = 1; k <= m; k++) {
        scanf("%d%d%d", &i[k], &j[k], &w[k]);
    }
    scanf("%d", &s);

    int key[51], parent[51], ok = 0, finish[51];

    for (int k = 1; k <= n; k++) {
        key[k] = 10001;
        parent[k] = -1;
        finish[k] = 0;
    }
    key[s] = 0;
    int u = s; // u 正在處理幾號
    finish[s] = 1; // 幾號處理好了


    while (ok != n) {
        for (int k = 1; k <= n; k++) {
            key[u] = 10001;
            if (key[k] < key[u] && finish[k] == 0) {
                u = k;
            }
        }
        finish[u] = 1;

        for (int k = 1; k <= m; k++) {
            if (u == i[k] && key[j[k]] > w[k] && finish[j[k]] == 0) {
                key[j[k]] = w[k];
                parent[j[k]] = u;
            }
            if (u == j[k] && key[i[k]] > w[k] && finish[i[k]] == 0) {
                key[i[k]] = w[k];
                parent[i[k]] = u;
            }
        }
        ok++;
    }

    for (int k = 1; k <= n; k++) {
        printf("%d ", parent[k]);
    }

}