#include<bits/stdc++.h>
using namespace std;
int h[500001],nxt[1000001],val[1000001],zd[1000001],cnt=0;
int n,m,s;
long long dis[500001];
bool inq[500001];
int q[10000001],f,e;
void addedge(int a,int b,int c){
    cnt++;
    val[cnt]=c,zd[cnt]=b,nxt[cnt]=0;
    nxt[cnt]=h[a];
    h[a]=cnt;
}
signed main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        addedge(a,b,c);
    }
    memset(dis,-1,sizeof(dis));
    dis[s]=0,inq[s]=1;
    q[1]=s,f=1,e=1;
    while(f<=e){
        int u=q[f++];
        for(int p=h[u];p;p=nxt[p]){
            int v=zd[p],c=val[p];
            if(dis[v]==-1||dis[v]>dis[u]+c){
                dis[v]=dis[u]+c;
                if(inq[v]==0)q[++e]=v,inq[v]=1;
            }
        }
        inq[u]=0;
    }
    for(int i=1;i<=n;i++){
        if(dis[i]!=-1)printf("%d ",dis[i]);
        else printf("-1 ");
    }
}

写了个 SPFA 过不了，求助 /kk