//无向图,单调队列优化 
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
struct NODE
{
	ll w;
	ll to;
}l;
vector<NODE> road[1000001];
ll n,m;//节点的个数以及边数
ll dis[1000001];
//dis[i]表示从起点到i号点的最短路径长度
bool vis[1000001];
//vis[i]=true表示i号节点已经被访问过了 
ll qidian,zhongdian;//起点,终点 
priority_queue<pair<int,int>/*c++中的一种结构体pair,排序时以第一个数来排*/> q;
//第一个存dis值,第二个位置存点的编号 
int main()
{
	scanf("%lld%lld",&n,&m); 
	ll i,j,a,b,c;
	for(i=1;i<=n;i++)
		dis[i]=0x7fffffff;
	scanf("%lld",&qidian);
	dis[qidian]=0;
	q.push(make_pair(0,1));
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		l.w=c;
		l.to=b;
		road[a].push_back(l);
		l.to=a;
		road[b].push_back(l);
	}
	while(!q.empty())
	{
		i=q.top().second;// 
		q.pop();
		if(vis[i]==true)
			continue;
		vis[i]=true;
		for(j=0;j<road[i].size();j++)
		{
			if(dis[road[i][j].to]>dis[i]+road[i][j].w)
			{
				dis[road[i][j].to]=dis[i]+road[i][j].w;
				q.push(make_pair(-dis[road[i][j].to]/*变负数使大根堆当小根堆来用*/,road[i][j].to));
			}
		}
	}
	for(i=1;i<=n;i++)
		printf("%lld ",dis[i]);
	return 0;
}