// 朴素Dijkstra O(n^2+m)
#include <bits/stdc++.h>
using namespace std;
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
#define PII pair<int,int>
const int N = 1e3+10,M = 1e6+10;
int n,m,s;
int h[N],e[M],ne[M],w[M],idx;
int dis[N],vis[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int rd()
{
    int x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = - 1;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x *= f;
}

void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    while(1)
    {
        int u=0;
        F(i,1,n)
          if(!vis[i] && dis[u] > dis[i])
            u = i ;
        if(u==0)break;
        vis[u]=1;
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(dis[j] > dis[u] + w[i])
              dis[j] = dis[u] + w[i];
        }
    }
}

signed main()
{
    
    memset(h,-1,sizeof h);
    cin>>n>>m>>s;
    F(i,1,m)
    {
        int a,b,c;
        a=rd(),b=rd(),c=rd();
        add(a,b,c); 
    }
    dijkstra();
    F(i,1,n)
      printf("%d ",dis[i]);
    return 0;
}