#include<bits/stdc++.h>
using namespace std;
long long n,m,s,mn[100100];
struct note{
	long long to,w;
};
vector<note> e[200100];
bool vis[100100];
void dij(int x){
	priority_queue<int> q;
	q.push(x);
	while(!q.empty()){
		int k=q.top();
		q.pop();
		if(vis[k])continue;
		vis[k]=1;
		for(int i=0;i<e[k].size();i++){
			if(mn[e[k][i].to]>mn[k]+e[k][i].w){
				mn[e[k][i].to]=mn[k]+e[k][i].w;
				if(!vis[e[k][i].to]){
					q.push(e[k][i].to);
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1,x,y,z;i<=m;i++){
		cin>>x>>y>>z;
		e[x].push_back({y,z});
	}
	for(int i=2;i<=n;i++)mn[i]=1e10;
	dij(1);
	for(int i=1;i<=n;i++)cout<<mn[i]<<" ";
	return 0;
}

#2#6对