下载过数据以证实好像是死循环
没有优化，我同学过了，我没过
救救孩纸

#include<iostream>
using namespace std;
int n,m,s,head[10005],next[100005],dx[100005],qz[100005];
int a,b,c,tot;
long long ans[10005];
bool flag[10005];
void add(int x,int y,int z){
	tot++;
	next[tot]=head[x];
	dx[tot]=y;
	qz[tot]=z;
	head[x]=tot;
}
void dijkstra(){
	ans[s]=0;
	while(1){
		int now=-1;
		for(int i=1;i<=n;i++)
			if(!flag[i]&&(now==-1||ans[i]<ans[now]))
				now=i;
		if(now==-1) break;
		flag[now]=1;
		for(int i=head[now];i;i=next[i])
			ans[dx[i]]=min(ans[dx[i]],ans[now]+qz[i]);
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++) ans[i]=2147483647;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		add(a,b,c);
	}
	dijkstra();
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
	return 0;
}