#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+40,inf=0x3f3f3f3f;//基本常数 
struct node{int v,w;};
int dist[maxn],n,m,s;
bool visited[maxn];
vector<node>graph[maxn];
priority_queue<pair<int,int> >q;//xu yao yong de 
void dijkstra(int s){
	memset(dist,inf,sizeof(dist));memset(visited,0,sizeof(visited));//chu shi hua
	dist[s]=0;q.push(make_pair(0,s));//xian jiang di yi ge dian cun chu jin lai
	while(!q.empty()){
		int u=q.top().second;//di yi ge dian de bian hao
		q.pop();
		if(visited[u]==true)continue;
		visited[u]=true;
		int size=graph[u].size();
		for(int j=0;j<size;j++){
			int v=graph[u][j].v,w=graph[u][j].w;
			if(dist[u]+w<dist[v]){
				dist[v]=dist[u]+w;q.push(make_pair(-dist[v],v));
			}
		}
	}
}
int main(){
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	cin>>n>>m>>s;
	dist[s]=0;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		graph[u].push_back({v,w});
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		if(dist[i]==inf){
			cout<<-1<<" ";
		}
		else cout<<dist[i]<<" ";//漏了这几句直接给我从AC干到30WA😕 
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}