#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstring>
using namespace std;

const int N = 1e5;
const int M = 2e5;
const int MAX = 0x3f3f3f3f;
int n, s, m;
int nex[M];
int to[M];
int head[N];
int w[M];
int dis[N];
int heap[N];
int wh[N];
int cnt = 1;
int hsize = 0;

void swap(int i, int j) {
    int temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
    wh[heap[i]] = i;
    wh[heap[j]] = j;
}
void built(int s, int t, int v) {
    nex[cnt] = head[s];
    to[cnt] = t;
    w[cnt] = v;
    head[s] = cnt++;
}

void inserth(int i) {
    while (  dis[heap[i]] < dis[heap[(i - 1) / 2]]) {
        swap(i, (i - 1) / 2);
       
        i = (i - 1) / 2;
    }
   
}

void hfy(int i) {
    int l = i * 2 + 1;
    while (l < hsize) {
        int best = l + 1 < hsize && dis[heap[l + 1]] < dis[heap[l]] ? l + 1 : l;
        best = dis[heap[best]] < dis[heap[i]] ? best : i;
        if (best == i) {
            break;
        }
        swap(best, i);
       
        i = best;
        l = i * 2 + 1;
    }
}

int pop() {
    int ans = heap[0];
    
    swap(0, --hsize);
    
    hfy(0);
    wh[ans] = -2;
    return ans;
}

void push(int v, int w) {
    if (wh[v] == -1) {
        heap[hsize] = v;
        wh[v] = hsize++;
        dis[v] = w;
        inserth(wh[v]);
    }
    else if (wh[v] >= 0) {
        dis[v] = min(dis[v], w);
            inserth(wh[v]);//1
        
    }
}

void built1() {
    hsize = 0;
    cnt = 1;
    fill(dis, dis + N, MAX);
    memset(head, 0, sizeof(head));
    memset(wh, -1, sizeof(wh));
}

int main() {
    cin >> n >> m >> s;
    built1();
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        built(u, v, w);
    }
    push(s, 0);
    while (hsize > 0) {
        int cur = pop();
        for (int i = head[cur]; i > 0; i = nex[i]) {
            push(to[i], dis[cur] + w[i]);
        }
    }
    cout << dis[1];
    for (int i = 2; i <= n; i++) { 
        cout << " " <<dis[i] ;
    }
    return 0;
}