#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define faster() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
 
typedef pair<int,int> ii ;
 
int n  , m , s ;
vector<ii> ke[200005];
bool visited[200005];
struct Edge{
    int u , v , w ;
};
vector<Edge> dsCanh ;
 
 
void BellmanFord(int s){
    vector<int> d(n + 1 , 1e9);
    d[s] = 0 ;
    for(int i = 1 ; i <= n - 1 ; i++){
        for(Edge e : dsCanh){
            int u = e.u ;
            int v = e.v ;
            int w = e.w ;
            if(d[u] < 1e9){
                d[v] = min(d[v] , d[u] + w);
            }
        }
    }
 
    for(int i = 1 ; i <= n ; i++){
        cout << d[i] << " ";
    }
}
 
void solve(){
    cin >> n >> m >> s ;
    for(int i = 1 ; i <= m ; i++){
        int x , y, w ; cin >> x >> y >> w ;
        ke[x].push_back({y , w});
        ke[y].push_back({x , w});
        // them ca 2 canh vao dsCanh
        dsCanh.push_back({x , y, w});
        dsCanh.push_back({y , x, w});
    }
    BellmanFord(s);
}
 
signed main() {
    faster(); 
    int test = 1 ; 
    // cin >> test ;
    while(test--)   solve();
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgZW5kbCAiXG4iCiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIGZhc3RlcigpIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShudWxscHRyKTsgY291dC50aWUobnVsbHB0cik7Cgp0eXBlZGVmIHBhaXI8aW50LGludD4gaWkgOwoKaW50IG4gICwgbSAsIHMgOwp2ZWN0b3I8aWk+IGtlWzIwMDAwNV07CmJvb2wgdmlzaXRlZFsyMDAwMDVdOwpzdHJ1Y3QgRWRnZXsKICAgIGludCB1ICwgdiAsIHcgOwp9Owp2ZWN0b3I8RWRnZT4gZHNDYW5oIDsKCgp2b2lkIEJlbGxtYW5Gb3JkKGludCBzKXsKICAgIHZlY3RvcjxpbnQ+IGQobiArIDEgLCAxZTkpOwogICAgZFtzXSA9IDAgOwogICAgZm9yKGludCBpID0gMSA7IGkgPD0gbiAtIDEgOyBpKyspewogICAgICAgIGZvcihFZGdlIGUgOiBkc0NhbmgpewogICAgICAgICAgICBpbnQgdSA9IGUudSA7CiAgICAgICAgICAgIGludCB2ID0gZS52IDsKICAgICAgICAgICAgaW50IHcgPSBlLncgOwogICAgICAgICAgICBpZihkW3VdIDwgMWU5KXsKICAgICAgICAgICAgICAgIGRbdl0gPSBtaW4oZFt2XSAsIGRbdV0gKyB3KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICBmb3IoaW50IGkgPSAxIDsgaSA8PSBuIDsgaSsrKXsKICAgICAgICBjb3V0IDw8IGRbaV0gPDwgIiAiOwogICAgfQp9Cgp2b2lkIHNvbHZlKCl7CiAgICBjaW4gPj4gbiA+PiBtID4+IHMgOwogICAgZm9yKGludCBpID0gMSA7IGkgPD0gbSA7IGkrKyl7CiAgICAgICAgaW50IHggLCB5LCB3IDsgY2luID4+IHggPj4geSA+PiB3IDsKICAgICAgICBrZVt4XS5wdXNoX2JhY2soe3kgLCB3fSk7CiAgICAgICAga2VbeV0ucHVzaF9iYWNrKHt4ICwgd30pOwogICAgICAgIC8vIHRoZW0gY2EgMiBjYW5oIHZhbyBkc0NhbmgKICAgICAgICBkc0NhbmgucHVzaF9iYWNrKHt4ICwgeSwgd30pOwogICAgICAgIGRzQ2FuaC5wdXNoX2JhY2soe3kgLCB4LCB3fSk7CiAgICB9CiAgICBCZWxsbWFuRm9yZChzKTsKfQoKc2lnbmVkIG1haW4oKSB7CiAgICBmYXN0ZXIoKTsgCiAgICBpbnQgdGVzdCA9IDEgOyAKICAgIC8vIGNpbiA+PiB0ZXN0IDsKICAgIHdoaWxlKHRlc3QtLSkgICBzb2x2ZSgpOwogICAgcmV0dXJuIDA7Cn0K

MTAgNDQgNQo3IDUgNjAKOSA4IDMxCjkgMSA4Mwo0IDMgMjUKNiAyIDEKNCAxIDUyCjYgMyA3Ngo3IDYgOTUKOSA3IDg0CjggMiA5MQoxMCA3IDgKNiA0IDMyCjEwIDIgNzYKMyAxIDYyCjEwIDYgODgKOCAzIDEyCjUgMyAxNQo1IDQgNDAKOSAyIDIwCjMgMiA1CjUgMSAzNgo5IDQgOTgKOCA2IDY1CjggNSA5NQoxMCAzIDU1CjkgNiA5NQoxMCAxIDUKNCAyIDcwCjcgMSA4MAoxMCA0IDM1CjcgMiA5OQoxMCA5IDI0CjYgNSA5NAoyIDEgNzcKOCAxIDEyCjggNCA3Ngo5IDMgMjcKNSAyIDUKOSA1IDEyCjEwIDUgMQo4IDcgNTkKNiAxIDEKMTAgOCA5Mgo3IDMgNTQK

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