#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int N = ;

int head[N], cnt, n, m, s;

long long dis[N];

bool vis[N];

struct node {

    int next, to;

    long long w;

}e[N];

void add(int x, int y, long long z) {

    e[++cnt].next = head[x];

    e[cnt].to = y;

    e[cnt].w = z;

    head[x] = cnt;

}

void dijkstra(int s) {

    for(int i = ; i <= n; i++) dis[i] = ;

    dis[s] = ;

    for(int i = ; i <= n; i++) {

        int k = , maxn = ;

        for(int j = ; j <= n; j++)

            if(!vis[j] && dis[j] <= maxn)

                k = j, maxn = dis[j];

        vis[k] = ;

        for(int j = head[k]; j; j = e[j].next)

            if(dis[e[j].to] > dis[k] + e[j].w)

                dis[e[j].to] = dis[k] + e[j].w;

    }

}

int main () {

    scanf("%d%d%d", &n, &m, &s);

    for(int i = ; i <= m; i++) {

        int x, y;

        long long z;

        scanf("%d%d%lld", &x, &y, &z);

        add(x, y, z);

    }

    dijkstra(s);

    for(int i = ; i <= n; i++)

        printf("%lld ", dis[i]);

    return ;

}

#include <iostream>

#include <cstdio>

#include <queue>

#define N 500005

#define inf 2147483647

using namespace std;

int n, m, s, cnt;

int dis[N], vis[N], head[N];

struct node {

    int next, to, w;

}tr[N];

void add (int x, int y, int z) {

    tr[++cnt].to = y;

    tr[cnt].next = head[x];

    tr[cnt].w = z;

    head[x] = cnt;

}

void spfa () {

    queue<int> q;

    for (int i = ; i <= n; i++)

        dis[i] = inf;

    vis[s] = ;

    q.push(s);

    dis[s] = ;

    while (!q.empty()) {

        int he = q.front();

        q.pop();

        vis[he] = ;

        for (int i = head[he]; i ;i = tr[i].next) {

            if (dis[tr[i].to] > dis[he] + tr[i].w) {

                dis[tr[i].to] = dis[he] + tr[i].w;

                if (!vis[tr[i].to]) {

                    vis[tr[i].to] = ;

                    q.push(tr[i].to);

                }

            }

        }

    }

}

int main () {

    scanf ("%d%d%d", &n, &m, &s);

    for (int i = ; i <= m; i++) {

        int a, b, c;

        scanf ("%d%d%d", &a, &b, &c);

        add (a, b, c);

    }

    spfa ();

    for (int i = ; i <= n; i++)

        if (s == i) printf ("0 ");

        else printf ("%d ", dis[i]);

    return ;

}

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int N = ;

int n, m, s, cnt, head[N], dis[N];

bool vis[N];

struct node{

    int next, to, w;

}e[N];

int read() {

    int s = , w = ;

    char ch = getchar();

    while(!isdigit(ch)){if(ch == '-') w = -;ch = getchar();}

    while(isdigit(ch)){s = s *  + ch - '';ch = getchar();}

    return s * w;

}

void add(int x, int y, int z) {

    e[++cnt].next = head[x];

    e[cnt].to = y;

    e[cnt].w = z;

    head[x] = cnt;

}

struct Node {

    int u, v;

    bool operator<(const Node &b) const {

        return u > b.u;

    }

};

void dijikstra(int s) {

    priority_queue <Node> q;

    memset(dis, 0x3f3f3f3f, sizeof(dis));

    dis[s] = ;

    Node o;

    o.u = ;

    o.v = s;

    q.push(o);

    while(!q.empty()) {

        int u = q.top().v;

        int d = q.top().u;

        q.pop();

        if(d != dis[u])continue;

        for(int i = head[u]; i; i = e[i].next) {

            int v = e[i].to;

            int w = e[i].w;

            if(dis[v] > dis[u] + w) {

                dis[v] = dis[u] + w;

                Node p;

                p.u = dis[v], p.v = v;

                q.push(p);

            }

        }

    }

}

int main () {

    n = read();

    m = read();

    s = read();

    while(m--) {

        int x, y, z;

        x = read();

        y = read();

        z = read();

        add (x, y, z);

    }

    dijikstra(s);

    for(int i = ; i <= n; i++)

        printf("%d ", dis[i]);

    return ;

}