#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii ;
vector<ii> adj[1001];
int n, m , s;
// dinh , canh , dinh bat dau
void inp(){
    cin >> n >> m >> s;
    for(int i = 1 ; i <= m ; i++){
        int x,y,z;
        cin >> x >> y >> z;
        adj[x].push_back({y,z});
        adj[y].push_back({x,z});
    }
}
void Dijkstra(int s){
    priority_queue<ii,vector<ii>,greater<ii>> q;
    q.push({0,s});
    vector<int> d(n + 1 , 1e9);
    d[s] = 0 ;
    while(!q.empty()){
        ii t = q.top();
        q.pop();
        int dis = t.first ;
        int u = t.second;
        if(dis > d[u]) continue;
        for(ii e : adj[u]){
            int v = e.first;
            int w = e.second;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                q.push({d[v],v});
            }
        }
    }
    for(int i = 1 ; i <= n ; i++){
        cout << d[i] << " ";
    }
}
int main(){
    inp();
    Dijkstra(s);
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IGlpIDsKdmVjdG9yPGlpPiBhZGpbMTAwMV07CmludCBuLCBtICwgczsKLy8gZGluaCAsIGNhbmggLCBkaW5oIGJhdCBkYXUKdm9pZCBpbnAoKXsKICAgIGNpbiA+PiBuID4+IG0gPj4gczsKICAgIGZvcihpbnQgaSA9IDEgOyBpIDw9IG0gOyBpKyspewogICAgICAgIGludCB4LHksejsKICAgICAgICBjaW4gPj4geCA+PiB5ID4+IHo7CiAgICAgICAgYWRqW3hdLnB1c2hfYmFjayh7eSx6fSk7CiAgICAgICAgYWRqW3ldLnB1c2hfYmFjayh7eCx6fSk7CiAgICB9Cn0Kdm9pZCBEaWprc3RyYShpbnQgcyl7CiAgICBwcmlvcml0eV9xdWV1ZTxpaSx2ZWN0b3I8aWk+LGdyZWF0ZXI8aWk+PiBxOwogICAgcS5wdXNoKHswLHN9KTsKICAgIHZlY3RvcjxpbnQ+IGQobiArIDEgLCAxZTkpOwogICAgZFtzXSA9IDAgOwogICAgd2hpbGUoIXEuZW1wdHkoKSl7CiAgICAgICAgaWkgdCA9IHEudG9wKCk7CiAgICAgICAgcS5wb3AoKTsKICAgICAgICBpbnQgZGlzID0gdC5maXJzdCA7CiAgICAgICAgaW50IHUgPSB0LnNlY29uZDsKICAgICAgICBpZihkaXMgPiBkW3VdKSBjb250aW51ZTsKICAgICAgICBmb3IoaWkgZSA6IGFkalt1XSl7CiAgICAgICAgICAgIGludCB2ID0gZS5maXJzdDsKICAgICAgICAgICAgaW50IHcgPSBlLnNlY29uZDsKICAgICAgICAgICAgaWYoZFt2XSA+IGRbdV0gKyB3KXsKICAgICAgICAgICAgICAgIGRbdl0gPSBkW3VdICsgdzsKICAgICAgICAgICAgICAgIHEucHVzaCh7ZFt2XSx2fSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBmb3IoaW50IGkgPSAxIDsgaSA8PSBuIDsgaSsrKXsKICAgICAgICBjb3V0IDw8IGRbaV0gPDwgIiAiOwogICAgfQp9CmludCBtYWluKCl7CiAgICBpbnAoKTsKICAgIERpamtzdHJhKHMpOwp9Cg==

MTAgNDQgNQo3IDUgNjAKOSA4IDMxCjkgMSA4Mwo0IDMgMjUKNiAyIDEKNCAxIDUyCjYgMyA3Ngo3IDYgOTUKOSA3IDg0CjggMiA5MQoxMCA3IDgKNiA0IDMyCjEwIDIgNzYKMyAxIDYyCjEwIDYgODgKOCAzIDEyCjUgMyAxNQo1IDQgNDAKOSAyIDIwCjMgMiA1CjUgMSAzNgo5IDQgOTgKOCA2IDY1CjggNSA5NQoxMCAzIDU1CjkgNiA5NQoKMTAgMSA1CjQgMiA3MAo3IDEgODAKMTAgNCAzNQo3IDIgOTkKMTAgOSAyNAo2IDUgOTQKMiAxIDc3CjggMSAxMgo4IDQgNzYKOSAzIDI3CjUgMiA1CjkgNSAxMgoxMCA1IDEKOCA3IDU5CjYgMSAxCjEwIDggOTIKNyAzIDU0

10 44 5
7 5 60
9 8 31
9 1 83
4 3 25
6 2 1
4 1 52
6 3 76
7 6 95
9 7 84
8 2 91
10 7 8
6 4 32
10 2 76
3 1 62
10 6 88
8 3 12
5 3 15
5 4 40
9 2 20
3 2 5
5 1 36
9 4 98
8 6 65
8 5 95
10 3 55
9 6 95

10 1 5
4 2 70
7 1 80
10 4 35
7 2 99
10 9 24
6 5 94
2 1 77
8 1 12
8 4 76
9 3 27
5 2 5
9 5 12
10 5 1
8 7 59
6 1 1
10 8 92
7 3 54