#求助，用set优化的dijkstra，tle前三个点

#include<bits/stdc++.h>
using namespace std;

typedef int itn;
typedef long long ll;
typedef pair<int, int> P;
const int MAX = 100005;

struct edge {
    int to;
    int cost;
};
vector<edge>a[MAX];
int d[MAX];
int vis[MAX];
set<P>s;//first:点编号  second:最短距离
void Dijkstra(int p) {
    s.insert(P(p, 0));
    while (s.size()) {
        int v = s.begin()->first;
        int dis = s.begin()->second;
        s.erase(s.begin());
        if (dis > d[v])continue;
        for (int i = 0; i < a[v].size(); i++) {
            edge e = a[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;

                s.insert(P(e.to, d[e.to]));
            }
        }
    }
}
int main() {
    int n, m, p;
    cin >> n >> m >> p;
    for (int i = 0; i < m; i++) {
        int from; 
        cin >> from;
        edge e;
        cin >> e.to >> e.cost;
        a[from].push_back(e);
    }
    memset(d, 0x3f, sizeof(d));
    d[p] = 0;
    Dijkstra(p);
    for (int i = 1; i <= n; i++)
    {
        cout << d[i] << " ";
    }
    return 0;
}