#include <iostream>
#include <limits.h>
#include <queue>
using namespace std;
int n, m, s, head[1000005], to[4000005], nxt[4000005], gsize, dis[1000005], ans[1000005];
int len[1000005];
bool f[1000005];
int cnt;
inline int read()
{ // 快读
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - 48, ch = getchar();
    return s * w;
}
inline void write(int x)
{ // 快写
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + 48);
}
void addedge(int u, int v, int l)
{
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    len[cnt] = l;
}

void SPFA(){
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        for(int i = head[u]; i; i = nxt[i]){
            int v = to[i];
            if(dis[u] + len[i] < dis[v]){
                dis[v] = dis[u] + len[i];
                if(!f[i]){
                    q.push(v);
                    f[i] = true;
                }
            }
        }
        q.pop();
        f[u] = false;
    }
}
int main()
{
    n = read();
    m = read();
    s = read();
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INT_MAX;
        head[i] = -1;
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y, l;
        x = read();
        y = read();
        l = read();
        addedge(x, y, l);
        addedge(y, x, l);
    }
    SPFA();
    ans[1] = 1;
    for (int i = 1; i <= n; i++)
    {
        write(dis[i]);
        cout << " ";
    }
    return 0;
}

4 * WA + 1 * TLE