#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 1LL<<60
int par[20010];
long long int dist[20100];
struct edge
{
    int u;
    long long int cost;
    edge(int a,int b)
    {
        u=a;
        cost=b;
    }
    bool operator <(const edge &p)const
    {
        return cost>p.cost;
    }
};
int n;
int grid[2010][2010];
long long int cost[2010][2010];
void dijkstra(int start)
{
    memset(par,-1,sizeof(par));
    for(int i=0; i<=n; i++)
        dist[i]=INF;
    priority_queue<edge>Q;
    Q.push(edge (start,0));
    dist[start]=0;
    while(!Q.empty())
    {
        edge top=Q.top();
        Q.pop();
        int u=top.u;
        for(int v=0; v<n; v++)
        {
            if(grid[u][v]==1)
            {
                if(dist[u]+cost[u][v]<dist[v])
                {
                    dist[v]=dist[u]+cost[u][v];
                    par[v]=u;
                    Q.push(edge(v,dist[v]));
                }
            }
        }
    }
    return;
}
int main()
{
    int t,m,st,end,u,v;
    long long int w;
    scanf("%d %d %d",&n,&m,&st);
    for(int i=0; i<m; i++)
    {
        scanf("%d %d %lld",&u,&v,&w);
        grid[u][v]=1;
        cost[u][v]= w;
    }
    dijkstra(st);
    for(int i=0;i<n;i++)
    printf(" %lld\n", dist[i]);
    return 0;
}
/*
O bssed index
3 6 2
0 1 100
1 0 100
0 2 200
2 0 200
1 2 50
2 1 50
*/