#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int err = (1<<31)-1;
typedef pair<int, int> pi;
const int N = 150050 ,M = 5e5+1000;
const int inf = 0x3f3f3f3f;
int h[N],idx, ne[M],e[M];
int dis[N];
int w[M];
bool st[N];
int n, m, s;
void add(int a, int b, int c)
{
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int dijkstra()
{
	priority_queue<pi,vector<pi>,greater<pi>> heap;
	heap.push({0,s});
	while(heap.size())
	{
		auto t = heap.top();
		heap.pop();//取出当前最小的点
		
		int ver = t.second, dist = t.first;
		if(st[ver])continue;//看是否是冗余
		st[ver] = true;
		
		for(auto i = h[ver]; i != -1; i = ne[i])
		{
			int j = e[i];
			if(dis[j] > dist + w[i])
			{
				dis[j] = dist + w[i];
				heap.push({dis[j],j});
			}
			
		}
	}
	if(dis[n] == inf)return -1;
	else return dis[n];
}
//priority_queue 1061109567
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m >> s;
	memset(h,-1,sizeof h);
	memset(dis,inf, sizeof(dis));
	dis[s] = 0;
	while(m--){
		int x, y, z;
		cin >> x >> y >> z;
		//		w[x][y] = min(w[x][y], z);
		add(x, y, z);
	}
	dijkstra();
	//	printf("%d\n",t);/
	for(int i = 1; i <= n; ++ i)
	{		
			if(dis[i] != -1)
			cout << dis[i] <<" ";
			else cout << INT_MAX << " "; 
	}
	//	if(dis[n] < inf)
	//	{
	//		cout << dis[n] << endl;
	//	}else{
	//		cout <<"-1" << endl;
	//	}
}