#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int g[108][108];
int n, m;
int used[108];
int dest[107];

int main()
{
    int i, v1, v2, len;
    for (i = 0; i < n; i++)
    {
        int j;
        used[i] = 0;
        dest[i] = 10000000;
        for (j = 0; j < n; j++)
            g[i][j] = -1;
    }
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++)
    {
        scanf("%d%d%d", &v1, &v2, &len);
        g[v1][v2] = g[v2][v1] = len;
    }

    int start;
    scanf("%d", &start);
    dest[start] = 0;
    int c, u;
    for (c = 0; c < (n - 1); c++)
    {
        int min = 10000000;
        for (i = 0; i < n; i++)
        {
            if (used[i] == 0 && dest[i] <= min)
            {
            min = dest[i];
            u = i;
            }
        }
        used[u] = 1;
        for (i = 0; i < n; i++)
        {
            if (used[i] == 0 && g[u][i] != -1 && dest[u] + g[u][i] < dest[i])
            {
                dest[i] = dest[u] + g[u][i];
            }
        }
    }

    for (i = 0; i < n; i++)
    {
        printf("%d ", dest[i]);
    }

    return 0;
}