#include <bits/stdc++.h>
using namespace std;
const int Mv = 100005,Me = 300005;
bool vis[Mv];
int Head[Mv],cnt = 1,dis[Mv];
struct Node{
    int to,nxt,cost;
};//链式前向星
Node Edge[Me];
void add(int a,int b,int c){
    Edge[cnt].nxt = Head[a];
    Edge[cnt].to = b;
    Edge[cnt].cost = c;
    Head[a] = cnt++;
}
struct ID{
    int mayu,cost;
    bool operator < (const ID a)const{
        return cost > a.cost;
    }
};
void Dijstra(int s){
    int u,v;
    priority_queue <ID> Q;
    ID temp;
    dis[s] = 0;
    temp.cost = 0,temp.mayu = s;
    Q.push(temp);
    while(!Q.empty()){
        temp = Q.top(),Q.pop();
        u = temp.mayu;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int p = Head[u];p;p=Edge[p].nxt){
            v = Edge[p].to;
                if(dis[v] > dis[u]+Edge[p].cost){
                    dis[v] = dis[u]+Edge[p].cost;
                    temp.cost = Edge[p].cost;
                    temp.mayu = Edge[p].to;
                    Q.push(temp);
                }
        }
    }
}


int main()
{
    int v,e,a,s,b,c;
    scanf("%d%d%d",&v,&e,&s);
    memset(dis,0x3f,sizeof(dis));
    for(int i = 1;i<=e;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    Dijstra(s);
    for(int i = 1;i <= v; i++) printf("%d ",dis[i]);
    return 0;
}