#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int maxn = 100005,INF = 99999999;
int n,m,s;
struct node{
	int to,w;
};
vector<node> e[maxn];
int dis[maxn];
bool vis[maxn];

void dijkstra() {
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	vis[s] = true;
	while(!q.empty()) {
		int p = q.front(); q.pop();
		cout<<"pop "<<p<<endl;
		int size = e[p].size();
		int minP = INF, minPos = 0; // 最小值，最小值对应的点 
		for(int i=0;i<size;i++) {
			int t = e[p][i].to;
			int w = e[p][i].w;
			dis[t] = min(dis[t],dis[p]+w);
			if(dis[t] < minP && !vis[t]) {
				minP = dis[t];
				minPos = t;
			}
		}
		if(minP != INF) {
			vis[minPos] = true;
			q.push(minPos);
		}
	}
}

int main(){
	cin>>n>>m>>s;
	int u,v,w;
	for(int i=1;i<=m;i++) {
		cin>>u>>v>>w;
		node p; p.to = v; p.w = w;
		e[u].push_back(p);
	}
	for(int i=1;i<=n;i++)
		dis[i] = INF;
	dijkstra();
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<" ";
	return 0;
}