#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 100000000
using namespace std;
typedef long long ll;

const int inf=1e9;
const int N=2e5+9;

struct edge{
	int to,cost;
};
typedef pair<int, int> P;

vector<edge> e[10001];
int d[10001],used[10001];
int n,m,s;

int main()
{
	cin>>n>>m>>s;
	while(m--){
		int u;
		edge temp;
		cin>>u>>temp.to>>temp.cost;
		e[u].push_back(temp);
	}
	
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d+1,d+1+n,inf);
	d[s]=0;
	used[s]=1;
	que.push(P(0,s));
	
	while(!que.empty()){
		int u=que.top().second; que.pop();
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].to,w=e[u][i].cost;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!used[v]){
					used[v]=1;
					que.push(P(d[v],v));
				}
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<d[i]<<' ';
	cout<<endl;
}