#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts;
struct edge {
    long long v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
    bool operator < (const edge& e2) const{
        return w > e2.w;
    }
};
vector<edge> edges[100005];
long long dis[100005];
bool inqueue[100005];
bool visited[100005];
void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
void dijkstra() {
    priority_queue<edge> pq;
        dis[ts] = 0;
    pq.push(edge(ts,0));
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        if (visited[e.v])continue;
        visited[e.v] = true;
        //dis[e.v] = e.w;
        for (int i = 0; i < edges[e.v].size(); i++) {
            if (!visited[edges[e.v][i].v] && dis[edges[e.v][i].v] > dis[e.v] + edges[e.v][i].w) {
                //有可能存在一种情况：虽然没有轮到点i成为离已处理完毕的点集最近的点，但点i的距离值已经由其它处理中或处理完毕的点多次更新，所以松弛的第二个条件必须加入
                dis[edges[e.v][i].v] = dis[e.v] + edges[e.v][i].w;
                pq.push(edge(edges[e.v][i].v, dis[edges[e.v][i].v]));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    //SPFA();
    dijkstra();
    for(int i=1;i<=t;i++)cout << dis[i]<<" ";
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include<iomanip>
using namespace std;
int n, m, s;
struct edge {
    int g, w;
    edge(int g, int w) :g(g), w(w) {}
    bool operator < (const edge& e1) const{
        return this->w > e1.w;
    }
};
vector<edge> edges[100005];
int dis[100005];
bool visited[100005];
void dijkstra() {
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<edge> pq;
    pq.push(edge(s, 0));
    while (!pq.empty()) {
        edge node = pq.top();
        pq.pop();
        if (visited[node.g])continue;
        visited[node.g] = true;
        if (node.w >= dis[node.g])continue;
        dis[node.g] = node.w;
        for (int i = 0; i < edges[node.g].size(); i++) {
            edge & curE = edges[node.g][i];
            if(!visited[curE.g])pq.push(edge(curE.g, node.w + curE.w));
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int f, g, w;
        cin >> f >> g >> w;
        edges[f].push_back(edge(g, w));
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        if (dis[i] == 0x7f7f7f7f)cout << "2147483647 ";
        else cout << dis[i] << " ";
    }
}