#include<bits/stdc++.h>
using namespace std;
#define PI pair<int,int>
struct node{
	int v;
	int w;
};
int n,m,u,v,w,s;
vector<node> a[100005];
int dis[100005],h[100005];
priority_queue<PI,vector<PI>,greater<PI> > q;
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		a[u].push_back(node{v,w});
	}
	memset(dis,0x3f,sizeof(dis))；
	q.push(make_pair(0,s));
	while(!q.empty()){
		u=q.top().second;
		w=q.top().first;
		q.pop();
		if(h[u])continue;
		h[u]=1;
		for(int i=0;i<a[u].size();i++){
			v=a[u][i].v;
			w=a[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(dis[v],v));
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

//没问题,真的
#include<bits/stdc++.h>
using namespace std;
#define PI pair<int,int>
struct node{
	int v;
	int w;
};
int n,m,u,v,w,s;
vector<node> a[100005];
int dis[100005],h[100005];
priority_queue<PI,vector<PI>,greater<PI> > q;
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		a[u].push_back(node{v,w});
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){
		u=q.top().second;
		q.pop();
		if(h[u])continue;
		h[u]=1;
		for(int i=0;i<a[u].size();i++){
			v=a[u][i].v;
			w=a[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(dis[v],v));
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

http://czoj.com.cn/p/P1474/solution/64dc6fa06d209ba2cdd7c809