#include <bits/stdc++.h>
#define V 100005
#define INF 1000005

using namespace  std;

typedef pair<int, int> pii;
int n, m, s, q;
vector<pii> g[V];
vector<int> dist(V), cnt(V), p(V);

void dijkstra(int src) {
    dist.assign(V, INF);
    cnt.assign(V, 1);
    p.assign(V, 0);
    dist[src] = 0;
    set<pii> heap;
    heap.insert({dist[src], src});
    while (!heap.empty()) {
        int u = heap.begin() -> second;
        heap.erase(heap.begin());
        for (auto pp : g[u]) {
            int v = pp.first;
            int d = pp.second;
            if (dist[v] == dist[u] + d) cnt[v] += cnt[u];
            if (dist[v] > dist[u] + d) {
                if (dist[v] != INF) {
                    heap.erase(heap.find({dist[v], v}));
                }
                dist[v] = dist[u] + d;
                cnt[v] = cnt[u];
                p[v] = u;
                heap.insert({dist[v], v});
            }
        }
    }
}

int main(){
    cin >> n >> m;
    int x, y, z;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }
    cin >> s;
    dijkstra(s);
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
    return 0;
}