#include <bits/stdc++.h>
using namespace std;

// inf = 10^9
const int inf = 1e9;

// Representasi graf dan setup-setup lainnya
vector<pair<int, int>> adjList[100005];
bool vis[100005];
int dst[100005];

int main() {
    // inputin graf
    // n banyak node, m banyak jalan (edge), start : start dari node yg mana
    int n, m, start;
    cin >> n >> m >> start;
    for(int i = 1; i <= m; i++) {
        // u : start, v : end, w : weight (jarak)
        int u, v, w;
        cin >> u >> v >> w;
        // undirected!! jadi butuh dua kali nyimpen (dari u ke v sama v ke u)
        adjList[u].push_back(make_pair(v, w));
        adjList[v].push_back(make_pair(u, w));
    }
    // set dst semua node (kecuali start) = inf, vis = false
    for(int i = 0; i < n; i++) vis[i] = false, dst[i] = inf;
    dst[start] = 0;
    // algo dijalankan
    // priority_queue dipake untuk menyimpan (dst[node], node) dari terkecil
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // masukin node start
    pq.push(make_pair(dst[start], start));
    while(!pq.empty()) {
        // dapetin elemen teratas dari pq
        int curnode = pq.top().second;
        pq.pop();
        if(vis[curnode] == true) continue;
        // iterate semua neighbor dari curnode
        for(auto i : adjList[curnode]) {
            int nextnode = i.first, weight = i.second;
            // kalo ternyata ada jarak yang minimum, kita update dan push ke pq
            if(dst[nextnode] > dst[curnode] + weight) {
                dst[nextnode] = dst[curnode] + weight;
                pq.push(make_pair(dst[nextnode], nextnode));
            }
        }
        // set visited = true
        vis[curnode] = true;
    }
    for(int i = 0; i < n; i++) cout << dst[i] << ' ';
    cout << '\n';
}