#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,st;
struct node{
	int n;
	int l;
	int b;
	bool operator<(const node&b)const
	{return l>b.l;}
};
priority_queue<node>q;
vector<node>a[2000000];
node dp[2000000];
int main(){
  	int i,j,k,p;
  	node x,y;
  	cin>>n>>m>>st;
  	for(i=1;i<=m;i++){
  		cin>>x.n>>y.n>>x.l;
  		y.l=x.l;
  		a[x.n].push_back(y);
  		a[y.n].push_back(x); 
	  }
    for(i=1;i<=n;i++)
    dp[i].l=-1;
    dp[st].b=0;
    y.l=0; y.n=st; y.b=0;
    q.push(y);
    while(!q.empty()){
    	x=q.top();
    	q.pop();
    	if(dp[x.n].l==-1){
    		dp[x.n]=x;
    		for(i=0;i<a[x.n].size();i++){
    			y.l=a[x.n][i].l+x.l;
    			y.n=a[x.n][i].n;
    			y.b=x.n;
    			q.push(y); 
			}
		}
	}
    for(i=1;i<=n;i++)
	cout<<dp[i].l<<" ";
  }

3个WA，求调