#include<bits/stdc++.h>
using namespace std;
const int N=10005;
const int INF=0x3f3f3f3f;
int n,m;
int dist[N],path[N],flag[N];

struct edge{
	int to,w;
	edge(int _to,int _w){
		to=_to;
		w=_w;
	}
};

vector<edge> G[N];//邻接表存图 

void init()
{
	memset(G,0x3f,sizeof(G));
	memset(dist,0x3f,sizeof(dist));
	memset(path,-1,sizeof(path));
	memset(flag,0,sizeof(flag));
}

struct node{
	int id,dis;
	node(){};
	node(int _id,int _dis){
		id=_id;dis=_dis;
	}
	bool operator < (const node &a)const{
		return a.dis<dis;
	}
};

void dijkstra(int u)
{
	priority_queue<node> q;
	dist[u]=0;//初始化 
	q.push(node(1,0));
	while(!q.empty())
	{
		node x=q.top();
		q.pop();
		if(flag[x.id]==1)  continue;
		flag[x.id]=1;// 第三步  松弛操作
		for(int i=0;i<G[x.id].size();i++)
		{
			edge v=G[x.id][i];
			if(v.w+x.dis<dist[v.to]&&!flag[v.to])
			{
				dist[v.to]=v.w+x.dis;
				path[v.to]=x.id;
				q.push(node(v.to,dist[v.to]));
			}
		} 
	}
}
void print_path(int u)
{
	if(u==1)  
	{
		cout<<u<<" ";
		return;
	}
	else {
		print_path(path[u]);
		cout<<u<<" ";
	}
}
signed main()
{
	int u,v,w;
	int s;
	cin>>n>>m;
	cin>>s;
	init();
	while(m--)
	{
		cin>>u>>v>>w;
		G[u].push_back(edge(v,w)); 
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<dist[i]<<" ";
		//print_path(i);
		//cout<<endl;
	}
}