#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;

#define Max 100010
#define INF 2147483647

vector<pair<int,int> > v[2 * Max];
int dis[Max];

void Dijkstra(int x){
    dis[x] = 0;
    priority_queue<pair<int,int> > q;
    q.push(make_pair(-dis[x],x));
    while(!q.empty()){
        int now = q.top().second;
        q.pop();
        for (int i = 0; i < v[now].size(); i++){
            int t = v[now][i].first;
            if(dis[t] > dis[now] + v[now][i].second){
                dis[t] = dis[now] + v[now][i].second;
                q.push(make_pair(-dis[t],t));
            }
        }
    }
}

int main(void){
    int n,m,s;
    cin >> n >> m >> s;
    int a,b,c;
    for (int i = 0; i < m; i++){
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
    }
    fill(dis+1,dis+n+1,INF);
    Dijkstra(s);
    for (int i = 1; i <= n; i++){
        if(i == 1) printf("%d",dis[i]);
        else printf(" %d",dis[i]);
    }
    return 0;
}

大佬们，该怎么优化啊