#include <bits/stdc++.h>
using namespace std;
int _x;char _c;
int read(){
	_x=0;_c=getchar();
	while(_c<'0'||_c>'9')_c=getchar();
	while(_c<='9'&&_c>='0'){
		_x=(_x<<1)+(_x<<3)+(_c^'0');
		_c=getchar();
	}
	return(_x);
}
int top;
int pre[200005],dis[200005];
bool v[200005];
class point{
	public:
		int id,dis;
		const bool operator >(const point& other)const{
			return(dis>other.dis);
		}
}now;
class node{
	public:
		int l,r,s;
}edge[200005];
inline void work(int l,int r,int s){
	++top;
	edge[top].l=pre[l];
	edge[top].r=r;
	edge[top].s=s;
	pre[l]=top;
}
priority_queue< point,vector<point>,greater<point> >q;
int n,m,s,l,r,k;
int main(){
	n=read();
	m=read();
	s=read();
	for(register int i=1;i<=m;i++)dis[i]=0x7fffffff;
	pre[s]=dis[s]=0;
	for(int i=1;i<=m;i++){
		l=read();
		r=read();
		k=read();
		work(l,r,k);
	}
	q.push((point){s,0});
	while(!q.empty()){
		now=q.top();
		if(!v[now.id]){
			v[now.id]=true;
			for(int i=pre[now.id];i>0;i=edge[i].l){
				if(dis[edge[i].r]>dis[now.id]+edge[i].s){
					dis[edge[i].r]=dis[now.id]+edge[i].s;
					if(!v[edge[i].r])q.push((point){edge[i].r,dis[edge[i].r]});
				}
			}
		}
		q.pop();
	}
	for(int i=1;i<=n;i++)printf("%d ",dis[i]);
	return(0);
}

一直在用，结果昨天才发现是假的

最离谱的能过洛谷数据