#include<bits/stdc++.h>
using namespace std;
int n;
int start; 
//邻节点 
struct adjNode{
	int index;
	int val;//此处val是边长
	adjNode *next;
};
//头结点 
struct headNode{
	int val;
	adjNode* first;
};
//图 
struct Gragh{
	headNode head[int(1e4+1)];
};

//连接边 
void insertedge(Gragh &G,int i,int j,int value){
	adjNode *tmp;
	tmp = new adjNode;
	tmp->index = j;
	tmp->val = value;
	tmp->next = G.head[i].first;
	G.head[i].first = tmp;
}

//构造邻接表 
void creat(Gragh &G){
	int m;
	cin>>n>>m>>start;
	//初始化头结点 
	for(int i = 1;i<=n;i++){
		G.head[i].val = i;
		G.head[i].first = nullptr;
	}
	for(int i = 1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		insertedge(G,u,v,w);
	}
}

//优先队列节点 
struct minNode{
	long long v;
	long long index;
	
	bool operator< (const minNode &t)const
	{
		return t.v<v;
	}
};

vector<long long>dij(Gragh& G,int root){
	priority_queue<minNode>que;
	//distance[i]原点到i的距离 
	vector<long long>dis(n+1,INT_MAX);
	dis[root] = 0;
	que.push({0,root});
	while(!que.empty())
	{ 
		minNode cur = que.top();
		que.pop();
		if(dis[cur.index]<cur.v) continue;
		
		//更新相邻点
		adjNode* i = G.head[cur.index].first;
		while(i!=nullptr){
			if(dis[i->index] > dis[cur.index]+i->val){
				dis[i->index] = dis[cur.index]+i->val;
				que.push({dis[i->index],i->index});
			}
			i=i->next;
		}
	}
	return dis;
}

int main(){
	Gragh G;
	creat(G);
	vector<long long>ans = dij(G,start);
	//遍历输出 
	for(long long i = 1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}