RT，用的朴素dij，在这道题中改下能过，但这道题爆了2，9，10点

#include<bits/stdc++.h>
using namespace std;
int n,m,s,u,v,w;
const int inf=2147483647;
struct edge{
	int to,next,dis;
}edge[400005];
int h[100005],cnt=0;
void AddEdge(int x,int y,int dis){
	edge[++cnt].to=y;
	edge[cnt].dis=dis;
	edge[cnt].next=h[x];
	h[x]=cnt;
}
long long dis[100005];bool flag[100005];
inline void dijkstra(int start){
	for(int i=1;i<=n;i++)dis[i]=inf;
	long long v0=start,minn=inf,minx,flaged=true;
	dis[v0]=0;
	while(flaged){
		flag[v0]=true;
		for(int i=h[v0];i;i=edge[i].next){
			if(edge[i].dis+dis[v0]<dis[edge[i].to]){
				dis[edge[i].to]=edge[i].dis+dis[v0];
			}
		}
		flaged=false;minn=inf;
		for(int i=1;i<=n;i++)if(dis[i]<=minn&&flag[i]==false)minn=dis[i],minx=i,flaged=true;
		v0=minx;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		AddEdge(u,v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)printf("%d ",dis[i]);
	return 0;
}