#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <iostream>
using namespace std;
#define INF pow(2,31)-1
int disk[10011];
int pre[10011];
int n, m, s;
priority_queue<pair<int, int>> q;
struct point {
	vector<int>v;
	vector<int>w;	
};
vector<point> a;
void dijkstra(int s)
{
	fill(disk, disk + 1001, INF);
	fill(pre, pre + 1001, 0);
	disk[s] = 0; q.push(make_pair(s, disk[s]));
	while (!q.empty())
	{
		int u = q.top().first, w = q.top().second;
		q.pop();
		pre[u] = 0;
		for (int i = 0; i < a[u].v.size(); i++)
		{
			int v = a[u].v[i], w = a[u].w[i];
			if (disk[u] == INF)
			{
				break;
			}
			if (disk[v] > disk[u] + w)
			{
				disk[v] = disk[u] + w;
				if (pre[v] == 0)
				{
					q.push(make_pair(v, disk[v]));
					pre[v] = -1;
				}
			}
		}
	}
}
void read()
{
	for (int i = 0; i < m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		a[u].v.push_back(v), a[u].w.push_back(w);
	}
}
int main()
{
	cin >> n >> m >> s;	
	a.resize(m+1);
	read();
	dijkstra(s);
	for (int i = 1; i <= n; i++)
	{
		cout << disk[i] << " ";
	}	
}