#include <bits/stdc++.h>
#define INF 1<<30
#define pii pair<int,int>
using namespace std;
int dis[1001000];
vector<pii>vec[1001000];
int n,m,s,vis[1001000];
void dj(){
	for (int i=1;i<=n;i++)dis[i]=INF;
	dis[1]=0;
	priority_queue<pii>q;
	q.push((pii){0,1});
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if (vis[x]){
			continue;	
		}
		vis[x]=1;
		for (int i=0,v,c;i<vec[x].size();i++){
			v=vec[x][i].first;
			c=vec[x][i].second;
			if (dis[v]>dis[x]+c){
				dis[v]=dis[x]+c;
				q.push((pii){dis[v],v});
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for (int i=1,x,y,c;i<=m;i++){
		cin>>x>>y>>c;
		vec[x].push_back((pii){y,c});
	}
	dj();
	for (int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}