#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1000100;
const ll maxm = 5000100;
const ll INF = 2147483647000;
ll Read() {
    ll num=0,f = 1; char ch = getchar();
    while(ch > '9' || ch < '0') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return num*f;
}
ll tot=0,n,m,s,u,v,w,dist[maxn],tage[maxn],head[maxm],to[maxm],next[maxm],value[maxm];
struct cmp{
    bool operator() (ll x,ll y) { return dist[x]>dist[y]; }
};
priority_queue<ll,vector<ll>,cmp > q;
void adde(ll x,ll y,ll z) {
    to[tot] = y;
    value[tot] = z;
    next[tot] = head[x];
    head[x] = tot++;
    return;
}
void dijkstra(ll x) {
    while(!q.empty()) q.pop();
    q.push(x);
    while(!q.empty()) {
        ll t = q.top();
        q.pop();
        if(tage[t] == 1) continue;
        tage[t] = 1;
        for(int i=head[t];i!=-1;i=next[i]) {
            ll y = to[i];
            dist[y] = min(dist[y],dist[t]+value[i]);
            q.push(y);
        }
    }
    return;
}
int main() {
     n = Read(); m = Read(); s = Read();
    memset(head,-1,sizeof(head));
    memset(tage,0,sizeof(tage));
    for(int i=1;i<=n;++i) {
        dist[i] = INF;
    }
    dist[s] = 0;
    for(int i=1;i<=m;++i) {
        u = Read(); v = Read(); w = Read();
        adde(u,v,w);
    }
    dijkstra(s);
    for(int i=1;i<=n;++i)
        printf("%lld ",dist[i]);
    return 0;
}

弱化版A掉了，标准版#1、#4过不去啊，球球了