#include <bits/stdc++.h>
#define INF 2147483647
using namespace std;
struct Edge
{
    int u, v, w;
    Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w){};
};
struct Node
{
    int n, v;
    Node(int _n, int _v) : n(_n), v(_v){};
    bool operator<(const Node &o) const
    {
        return v > o.v;
    }
};
int n, m, s, dis[10001];
vector<Edge> G;
void Dijkstra()
{
    priority_queue<Node> q;
    q.push(Node(s, 0));
    dis[s] = 0;
    while (!q.empty())
    {
        Node top = q.top();
        q.pop();
        if (dis[top.n] != INF)
            continue;
        dis[top.n] = top.v;
        for (vector<Edge>::iterator i = G.begin(); i != G.end(); i++)
            if ((*i).u == top.n)
                q.push(Node((*i).v, (*i).w + top.v));
    }
}
int main()
{
    memset(dis, INF, sizeof(dis));
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G.push_back(Edge(u, v, w));
    }
    Dijkstra();
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", dis[i]);
    }
    return 0;
}