#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1000;

struct State
{
    int to, price;
    State( int t, int p ) : to(t), price(p) {}
    bool operator<( const State& s ) const
    {
        if( price == s.price )
            return to < s.to;
        return price > s.price;
    }
};

int N, M, start;

vector<State> v[MAXN];

void input()
{
    scanf("%d %d", &N, &M);
    int first, second, price;
    for( int i = 0; i < M; i++ )
    {
        scanf("%d %d %d", &first, &second, &price);
        v[first-1].push_back(State(second-1, price));
        v[second-1].push_back(State(first-1, price));
    }
    scanf("%d", &start);
    start--;
}

void dijkstra()
{
    bool used[MAXN];
    memset(used, 0, sizeof(used));

    int dist[MAXN];
    memset(dist, 63, sizeof(dist));
    dist[start] = 0;

    priority_queue<State> pq;
    pq.push(State(start, 0));

    while( !pq.empty() )
    {
        int vertex = pq.top().to;
        pq.pop();

        if( used[vertex] )
        {
            continue;
        }
        used[vertex] = 1;

        for( int i = 0; i < v[vertex].size(); i++ )
        {
            int to = v[vertex][i].to;
            int price = v[vertex][i].price;

            if( !used[to] && dist[to] > dist[vertex] + price )
            {
                dist[to] = dist[vertex] + price;
                pq.push(State(to, dist[to]));
            }
        }
    }

    for( int i = 0; i < N; i++ )
    {
        cout << dist[i] << " ";
    }
    cout << endl;
}

int main()
{
    input();
    dijkstra();

    return 0;
}
/**

6 9
1 2 10
1 6 10
4 5 5
6 5 3
5 3 10
4 3 2
1 4 1
2 4 5
2 3 4
1

**/