// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<algorithm> #include<queue> #define spfa zhx_ak_ioi using namespace std; const long long inf=2147483647; long long n,m,s; long long dis[10008],vis[10001],head[10001],num_edge=0; struct Edge{ long long next,to,dis; }edge[500008]; queue <long long> q; void addedge(long long from,long long to,long long dis) { num_edge++; edge[num_edge].next=head[from]; edge[num_edge].to=to; edge[num_edge].dis=dis; head[from]=num_edge; } void spfa() { for(long long i=1;i<=n;++i) { dis[i]=inf; vis[i]=0; } dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { long long u=q.front(); q.pop(); vis[u]=0; for(long long i=head[u];i;i=edge[i].next) { long long zhongdian=edge[i].to; if(dis[zhongdian]>dis[u]+edge[i].dis) { dis[zhongdian]=dis[u]+edge[i].dis; if(!vis[zhongdian]) { q.push(zhongdian); vis[zhongdian]=1; } } } } } int main() { scanf("%lld %lld %lld",&n,&m,&s); for(long long i=1;i<=m;++i) { long long u,v,w; scanf("%lld %lld %lld",&u,&v,&w); addedge(u,v,w); } spfa(); for(long long i=1;i<=n;++i) { if(i==s) printf("0 "); else printf("%lld ",dis[i]); } return 0; }