#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,int> pii;
int head[100001],to[600001],nxt[600001],cnt;
long long w[600001],dis[100001];
bool vis[500001];
inline void add(int x,int y,long long z){
	nxt[++cnt]=head[x];
	head[x]=cnt;
	to[cnt]=y;
	w[cnt]=z;
}
priority_queue<pii,vector<pii>,greater<pii> >q;
int main(){
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	int x,y;
	long long z;
	for(int i=1;i<=m;++i){
		scanf("%d%d%lld",&x,&y,&z);
		add(x,y,z);
	}
//	for(int i=1;i<=k;++i){
//		scanf("%d%lld",&x,&z);
//		add(1,x,z);
//	}
	memset(dis,-1,sizeof(dis));
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		pii k=q.top();
		q.pop();
		int u=k.second;
		if(vis[u])continue;
		vis[u]=true;
		int i=head[u];
		while(i){
			if(dis[to[i]]>dis[u]+w[i]||dis[to[i]]==-1){
				dis[to[i]]=dis[u]+w[i];
				q.push(make_pair(dis[to[i]],to[i]));
			}
			i=nxt[i];
		}
	}
	for(int i=1;i<=n;++i){
		printf("%d ",dis[i]);
	}
	return 0;
}