#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1e9;
 
int main() {
    int n, m; // n - liczba wierzchołków, m - liczba krawędzi
    cin >> n >> m;
 
    vector<vector<pair<int,int>>> graf(n + 1);
    // pair = (sąsiad, waga)
 
    for(int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graf[a].push_back({b, w});
        graf[b].push_back({a, w}); // usuń, jeśli graf skierowany
    }
 
    int start;
    cin >> start;
 
    vector<int> dist(n + 1, INF);
    dist[start] = 0;
 
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    // (odległość, wierzchołek)
    pq.push({0, start});
 
    while(!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
 
        if(d > dist[v]) continue;
 
        for(auto [to, w] : graf[v]) {
            if(dist[to] > dist[v] + w) {
                dist[to] = dist[v] + w;
                pq.push({dist[to], to});
            }
        }
    }
 
    // Wyniki
    for(int i = 1; i <= n; i++) {
        if(dist[i] == INF) 
            cout << "Brak drogi do " << i << endl;
        else
            cout << "Najkrotsza droga do " << i << " = " << dist[i] << endl;
    }
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgSU5GID0gMWU5OwoKaW50IG1haW4oKSB7CiAgICBpbnQgbiwgbTsgLy8gbiAtIGxpY3piYSB3aWVyemNob8WCa8OzdywgbSAtIGxpY3piYSBrcmF3xJlkemkKICAgIGNpbiA+PiBuID4+IG07CgogICAgdmVjdG9yPHZlY3RvcjxwYWlyPGludCxpbnQ+Pj4gZ3JhZihuICsgMSk7CiAgICAvLyBwYWlyID0gKHPEhXNpYWQsIHdhZ2EpCgogICAgZm9yKGludCBpID0gMDsgaSA8IG07IGkrKykgewogICAgICAgIGludCBhLCBiLCB3OwogICAgICAgIGNpbiA+PiBhID4+IGIgPj4gdzsKICAgICAgICBncmFmW2FdLnB1c2hfYmFjayh7Yiwgd30pOwogICAgICAgIGdyYWZbYl0ucHVzaF9iYWNrKHthLCB3fSk7IC8vIHVzdcWELCBqZcWbbGkgZ3JhZiBza2llcm93YW55CiAgICB9CgogICAgaW50IHN0YXJ0OwogICAgY2luID4+IHN0YXJ0OwoKICAgIHZlY3RvcjxpbnQ+IGRpc3QobiArIDEsIElORik7CiAgICBkaXN0W3N0YXJ0XSA9IDA7CgogICAgcHJpb3JpdHlfcXVldWU8cGFpcjxpbnQsaW50PiwgdmVjdG9yPHBhaXI8aW50LGludD4+LCBncmVhdGVyPHBhaXI8aW50LGludD4+PiBwcTsKICAgIC8vIChvZGxlZ8WCb8WbxIcsIHdpZXJ6Y2hvxYJlaykKICAgIHBxLnB1c2goezAsIHN0YXJ0fSk7CgogICAgd2hpbGUoIXBxLmVtcHR5KCkpIHsKICAgICAgICBhdXRvIFtkLCB2XSA9IHBxLnRvcCgpOwogICAgICAgIHBxLnBvcCgpOwoKICAgICAgICBpZihkID4gZGlzdFt2XSkgY29udGludWU7CgogICAgICAgIGZvcihhdXRvIFt0bywgd10gOiBncmFmW3ZdKSB7CiAgICAgICAgICAgIGlmKGRpc3RbdG9dID4gZGlzdFt2XSArIHcpIHsKICAgICAgICAgICAgICAgIGRpc3RbdG9dID0gZGlzdFt2XSArIHc7CiAgICAgICAgICAgICAgICBwcS5wdXNoKHtkaXN0W3RvXSwgdG99KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICAvLyBXeW5pa2kKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgaWYoZGlzdFtpXSA9PSBJTkYpIAogICAgICAgICAgICBjb3V0IDw8ICJCcmFrIGRyb2dpIGRvICIgPDwgaSA8PCBlbmRsOwogICAgICAgIGVsc2UKICAgICAgICAgICAgY291dCA8PCAiTmFqa3JvdHN6YSBkcm9nYSBkbyAiIDw8IGkgPDwgIiA9ICIgPDwgZGlzdFtpXSA8PCBlbmRsOwogICAgfQoKICAgIHJldHVybiAwOwp9Cg==

NSA2CjEgMiA0CjEgMyAyCjIgMyA1CjIgNCAxMAozIDUgMwo0IDUgNAox

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