//

//  dijkstra妯℃澘.cpp

//  algorithm

//

//  Created by david.xu on 2018/8/6.

//  Copyright 漏 2018骞?david.xu. All rights reserved.

//

//不能有负边权!

#include <stdio.h>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#define maxn 100010

#define pa pair<int,int>

using namespace std;

int n,m,s,dis[maxn];

bool vis[maxn];

priority_queue<pa,vector<pa>,greater<pa> > q;

struct edge{

    int val,to;

};

vector<edge> e[maxn];

void dijkstra()//dis[i] 表示从起点到i的最短距离

{

    for(int i=;i<=n;i++)

        dis[i]=;

    dis[s]=;

    q.push(make_pair(, s));

    while(!q.empty())

    {

        int x=q.top().second;

        q.pop();

        if(vis[x])

            continue;

        vis[x]=;

        for(int i=;i<e[x].size();i++)

        {

            int y=e[x][i].to;

            if(dis[x]+e[x][i].val<dis[y])

            {

                dis[y]=dis[x]+e[x][i].val;

                q.push(make_pair(dis[y], y));

            }

        }

    }

}

int main()

{

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

    for(int i=;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        edge tmp;

        tmp.to=y;

        tmp.val=z;

        e[x].push_back(tmp);

    }

    dijkstra();

    for(int i=;i<=n;i++)

        printf("%d ",dis[i]);

    return ;

}