#include<iostream>
#include<queue>
#include<vector>
using namespace std;
main(){
	int n,m,s,j,i,k,e,inf=2009000999;deque<int>q;
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>s; vector<pair<int,int> >a[n];
	vector<int>d(n,inf); vector<bool>f(n,true);
	for(;m;--m){ cin>>i>>j>>k;
		a[i].push_back({j,k}); a[j].push_back({i,k});}
	d[s]=0;q.push_back(s);f[i]=false;
	while(!q.empty()){ i=q.front();q.pop_front();f[i]=true;
		for(auto c:a[i]){ j=c.first;e=c.second;
			if(d[j]>d[i]+e){
				if(d[j]==inf){q.push_back(j);f[j]=false;}
				else if (f[j]){q.push_front(j);f[j]=false;}
				d[j]=d[i]+e;}}}
		for(auto b:d)cout<<b<<' ';}