dij+堆

v#include<cstdio>
#include<queue>
using namespace std;int l[100001],tot,dis[100001],s,n,m;
inline int read()//输入优化
{
    int d=1,f=0;char c;
    while(c=getchar(),c<48||c>57)if(c=='-')d=-1;f=(f<<3)+(f<<1)+c-48;
    while(c=getchar(),c>47&&c<58) f=(f<<3)+(f<<1)+c-48;
    return d*f;
}
struct node{int next,to,w;}e[500001];//边
struct heap{int u,d;};//堆
inline bool operator <(heap x,heap y){return x.d>y.d;}//小的在前面
inline void add(register int u,register int v,register int w){e[++tot]=(node){l[u],v,w};l[u]=tot;}//建边
bool vis[100001];//判断会不会重新走过。。。
inline void Dijstra_heap()
{
    for(register int i=0;i<=n;i++) dis[i]=2147483647;
    dis[s]=0;
    priority_queue<heap>q;
    q.push((heap){s,0});vis[s]=true;
    while(q.size())
    {
        heap u=q.top();q.pop();//取出堆顶
        int x=u.u,d=u.d;vis[x]=true;//标记
        for(register int i=l[x];i;i=e[i].next)//用其进行拓展
        {
            int y=e[i].to,w=e[i].w;
            if(dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;//转移
                if(!vis[y]) q.push((heap){y,dis[y]}),vis[y]=true;//没有标记过则标记并放入
            }
        }
        vis[x]=false;//记得取消标记（没有也可以）
    }
    return;
}
signed main()
{
    n=read();m=read();s=read();
    for(register int i=1,x,y,z;i<=m;i++) x=read(),y=read(),z=read(),add(x,y,z);//输入
    Dijstra_heap();//dij
    for(register int i=1;i<=n;i++) printf("%d ",dis[i]);//输出
}