#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class node;
class side;

class node{
public:
    int distance = 2147483647;
    int id;
    vector<side> s;
    bool flag = false;
};

bool operator>(const node &a, const node &b){return a.distance > b.distance;}

class side{
public:
    int x;
    int y;
    int value;
};

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

void Push(int k, node** map){
    (*map)[k].flag = true;
    while(!(*map)[k].s.empty()){
        (*map)[(*map)[k].s.back().y].distance = min((*map)[k].distance + (*map)[k].s.back().value , (*map)[(*map)[k].s.back().y].distance);
        if(!(*map)[(*map)[k].s.back().y].flag)
            q.push((*map)[(*map)[k].s.back().y]);
        (*map)[k].s.pop_back();
    }
    return;
}
void ini(int n, node** map){
    for(int i = 0; i < n; i++)
        (*map)[i].id = i;
}

int main(){
    int n = 0;
    int m;
    int s;
    scanf("%d%d%d", &n, &m, &s);
    node *map = new node[n + 1];
    ini(n + 1, &map);
    while(m--){
        int a;
        int b;
        int v;
        scanf("%d%d%d", &a, &b, &v);
        side t;
        t.value = v;
        t.x = a;
        t.y = b;
        map[a].s.push_back(t);
    }
    map[s].distance = 0;
    Push(s, &map);
    while(!q.empty()){
        node now = q.top();
        q.pop();
        Push(now.id, &map);
    }
    for(int i = 1; i <= n; i++)
        printf("%d ", map[i].distance);
    return 0;
}