#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)

using namespace std;
const int N=1e5+24;

struct edge{
    int to,w;
};

struct node {
  int dis, u;
  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> linker[N];
int dis[N];
bool vis[N];
priority_queue< node,vector<node>,greater<node> > q;
int n,m;

void dijkstra(int s){
    rep(i,1,n)
        dis[i]=2147483647;
    dis[s]=0;
    q.push((node){0,s});
    while(!q.empty())
    {
        int u=q.top().u;
        q.pop();
        // if(vis[u]) 
            // continue;
        vis[u]=1;
        for(auto& it:linker[u])
        {
            int v=it.to,w=it.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push((node){dis[v],v});
            }
        }
    }
}

signed main(){
    int s;
    cin>>n>>m>>s;
    rep(i,1,m)
    {
        int u,v,w;
        cin>>u>>v>>w;
        linker[u].push_back((edge){v,w});
    }
    dijkstra(s);
    rep(i,1,n)
        cout<<dis[i]<<' ';
}

像这种堆劣化的 SPFA 竟然还能 AC！