#include <bits/stdc++.h>
#define INF 2147483647
using namespace std;

int n,m,s,u,v,w;
vector<pair<int, int > > e[10005];
bool vis[10005];
int dis[10005];

void dij(int x ){
	priority_queue<pair<int ,int > >q;
	memset(vis,false,sizeof(vis));
	memset(dis,INF,sizeof(dis));
	dis[x]=0;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int now=q.top().second;
		q.pop();
		if(vis[now]){
			continue;
		}
		vis[now]=true;
		for(int i=0;i<e[now].size();i++){
			int t=e[now][i].first,w=e[now][i].second;
			if(dis[t] > dis[now] + w){
				dis[t] = dis[now] + w;
				q.push(make_pair(-dis[t] , t));
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		e[u].push_back(make_pair(v,w));
	}	
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<endl;
	}
	return 0;
}