关于某个死掉的算法……

using namespace std;
const int maxn=1e4+10,maxm=5e5+10;
int n,m,s;
struct edge{
	int v,w;
};
edge E[maxn];
vector<int>G[maxn];
void read(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i){
		int u,v,w; scanf("%d%d%d",&u,&v,&w);
		E[i]=(edge){v,w};
		G[u].push_back(i);
	}
}

int dis[maxn];
bool inq[maxn];
deque<int>q;
void SPFA(){
	fill(dis+1,dis+n+1,0x3f3f3f3f);
	q.push_front(s); dis[s]=0; inq[s]=true;
	long long sum=0; 
	while(!q.empty()){
		int u=q.front(),t=q.size(); q.pop_front();
		while(dis[u]>sum/t){
			q.push_back(u);
			u=q.front();
			q.pop_front();
		}
		sum-=dis[u],inq[u]=false;
		for(int i=0;i<G[u].size();++i){
			int v=E[G[u][i]].v,w=E[G[u][i]].w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				if(!inq[v]){
					if(!q.empty() and dis[v]<dis[q.front()]) q.push_front(v);
					else q.push_back(v);
					sum+=dis[v];
					inq[v]=true;
				}
			}
		}
	}
}

int main(){
	read(); SPFA();
	for(int i=1;i<=n;++i) printf("%d ",dis[i]==0x3f3f3f3f?INT_MAX:dis[i]);
	return 0;
}