#include <iostream>
#include <vector>
#include <set>
using namespace std;

const int INF = 1e9;

vector<int> dijkstra (vector<vector<pair<int, int>>> &graph, int start) {
    vector<int> dist(graph.size(), INF);
    dist[start] = 0;

    set<pair<int,int>> q;
    q.insert({dist[start], start});

    while(!q.empty()) {
        int nearest = q.begin() -> second;
        q.erase(q.begin());

        for (auto &[to, weight] : graph[nearest]) {
            if (dist[nearest] + weight < dist[to]) {
                q.erase({dist[to], to});
                dist[to] = dist[nearest] + weight;
                q.insert({dist[to], to});
            }
        }
    }
    return dist;
}

int main() {
    int vC, eC;
    cin >> vC >> eC;

    vector<vector<pair<int, int>>> graph (vC);
    for (int i = 0; i < eC; i++) {
        int a, b, weight;
        cin >> a >> b >> weight;
        // a--;
        // b--;
        graph[a].emplace_back(b, weight);
        graph[b].emplace_back(a, weight);
    }
    int start;
    cin >> start;
    // start--;

    vector<int> dist = dijkstra(graph, start);
    for (int i : dist)
        cout << i << " ";
    return 0;
}
