#include <bits/stdc++.h>
using namespace std;
namespace ShortestPath{
	const int maxN=1e4+10;
	bool vis[maxN];
	int dis[maxN];
	struct node{
		int num,val;
		bool operator <(const node& u)const{
			return val<u.val;
		}
	};
	vector<node> edges[maxN];
	int dijsktra(int s,int t){
		for(int i=0;i<maxN;i++){
			vis[i]=false;
			dis[i]=INT_MAX;
		}
		priority_queue<node> q;		
		dis[s]=0;vis[s]=false;q.push({s,0});
		while(!q.empty()){
			int u=q.top().num;q.pop();
			if(vis[u])continue;
			vis[u]=true;
			for(node i:edges[u]){
				if(dis[i.num]>dis[u]+i.val){
					dis[i.num]=dis[u]+i.val;
					q.push({i.num,dis[i.num]});
				}
			}
		}
		return dis[t];
	}
}
int main(){
	//freopen("test.txt","r",stdin);
	int n,m,s;cin>>n>>m>>s;
	long long u,v,l;
	while(m-->0){
		cin>>u>>v>>l;
		ShortestPath::edges[u].push_back({v,l});
		//ShortestPath::tabledis[u][v]=min(l,ShortestPath::tabledis[u][v]);
	}
	ShortestPath::dijsktra(s,s);
	for(int i=1;i<=n;i++){
		cout<<ShortestPath::dis[i]<<" ";
	}
	return 0;
}