#include <cstdio>
#include <algorithm>
#define N 1111
#define M 222222
#define INF 1111111111

using namespace std;

int ef[M],es[M],ev[M],next[M],first[N],c,n,m,d[N],s;
bool b[N];

void add(int x,int y,int z){
    next[++c]=first[x];first[x]=c;
    ef[c]=x;es[c]=y;ev[c]=z;
}

void dist(int s){
    for(int i=1;i<=n;i++) d[i]=INF;//заполняем бесконечностями массив расстояний
    d[s]=0;//расстояние до стартовой естественно равно нулю
    for (int i=1;i<=n;i++){
        int mind=INF,u=0;//mind - сам минимум, u - его номер
        for (int j=1;j<=n;j++)//находим среди непросмотренных вершину u с минимальным d[u]
            if ((d[j]<mind || u==0) && !b[j]){
                u=j;
                mind=d[j];
            }
        b[u]=1;//помечаем ее как просмотренную
        for (int h=first[u];h;h=next[h]) d[es[h]]=min(d[es[h]],d[u]+ev[h]);//пытаемся релаксировать все вершины ребрами, выходящими из u
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for (int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    dist(s);
    for (int i=1;i<=n;i++) printf("%d ",d[i]);
    return 0;
}