#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;
int n, m, sorce, target;
int dis[100010];
bool visited[100010];
struct Node{
	int from;
	int to;
	int weight;
};
struct dot{
	int from;
	int dis;
	bool operator < (const dot &d) const{
		return d.dis<dis;
	}
};
priority_queue<dot> q;
vector<Node> edges[100010];

void dijikstra(){
	memset(dis, 0x3d, sizeof(dis));
	memset(visited, 0, sizeof(visited));
	dot a; a.from=sorce; a.dis=0;
	q.push(a);
	dis[sorce]=0;
	visited[sorce]=true;
	while(!q.empty()){
		dot front=q.top(); q.pop();
		int u=front.from;
		for(int i=0;i<edges[u].size();i++){
			int t=edges[u][i].to;
			int w=edges[u][i].weight;
			dis[t]=min(dis[t], dis[u]+w);
			if(!visited[t]){
				dot x; x.from=t; x.dis=dis[t];
				q.push(x);
				visited[t]=true;
			}
		}
	}
	return;
}

void print(){
	for(int i=1;i<=n;i++) printf("%d ", dis[i]);
}

int main(){
	scanf("%d%d%d", &n, &m, &sorce);
	for(int i=0;i<m;i++){
		Node a;
		scanf("%d%d%d", &a.from, &a.to, &a.weight);
		edges[a.from].push_back(a);
	}
	dijikstra();
	print();
	return 0;
}