#include<cstdio>
#include<vector>
#include<queue>
#include<utility>

using namespace std;

const int NMAX =50000;
const int INF  =9999999;

typedef pair  < int, int > ii;
typedef vector< int >     vi;
typedef vector< ii >     vii;

vector<ii> G[NMAX + 5];


int main() {

    freopen("dijkastra.in"  ,"r",stdin );
    freopen("dijkastra.out","w",stdout);

    int n,m,s,u,v,w;
    int i;

    scanf("%d%d%d",&n,&m,&s);

    for(i=1; i<=m; ++i) {
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back(ii(v,w));
    }


    vi dist(n,INF);
    dist[s]=0;

    priority_queue<ii,vector<ii>,greater<ii> > pq;
    pq.push(ii(0,s));


    while(!pq.empty()) {

        ii front=pq.top();
        pq.pop();

        int d = front.first;
        u = front.second;
        if( d > dist[u])
            continue;

        for(int j=0 ; j < (int)G[u].size() ; ++j) {
            int v = G[u][j].first,duv = G[u][j].second;
            if(dist[u]+ duv < dist [v]) {
                dist[v]=dist[u] + duv;
                pq.push(ii(dist[v],v));
            }
        }
    }


    for( i=2; i<=n; ++i)
        printf("%d ",dist[i]);

    return 0;
}