#include <iostream>
#include <queue>
#include <algorithm>
#define mp make_pair
#define p pair<long long, long long>
using namespace std;
struct node
{
    long long to;
    long long next;
    long long dist;
} nd[200010];
long long h[200010];
long long dis[100010], vis[100010];
priority_queue<p> q;
long long tmp = 0;
void add(long long u, long long v, long long w)
{
    tmp++;
    nd[tmp].to = v;
    nd[tmp].dist = w;
    nd[tmp].next = h[u];
    h[u] = tmp;
}
int main()
{
    long long n, m, s;
    cin >> n >> m >> s;
    for (long long i = 0; i <= n; i++)
    {
        dis[i] = 0x7fffffff;
    }
    for (long long i = 0; i < m; i++)
    {
        long long u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    dis[s] = 0;
    q.push(mp(s, 0));
    while (!q.empty())
    {
        long long u = q.top().first;
        q.pop();
        if (vis[u])
        {
            continue;
        }
        vis[u] = 1;
        for (long long i = h[u]; i; i = nd[i].next)
        {
            long long v = nd[i].to;
            long long l = nd[i].dist;
            if (dis[v] > dis[u] + l)
            {
                dis[v] = dis[u] + l;
                q.push(mp(v, dis[v]));
            }
        }
    }
    for (long long i = 1; i <= n; i++)
    {
        cout << dis[i] << ' ';
    }
    return 0;
}

自我感觉写的怪怪的，但说不出哪里怪