#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

#define eps 1e-11
#define int long long
#define N 10005

struct edge 
{
	int to, val;
};

const int inf = LLONG_MAX / 2;
vector<edge> G[N];
int n, m, s, dis[N], book[N];

void add(int u, int v, int w) 
{
	G[u].push_back({v, w});
}
signed main() 
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) 
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	for (int i = 1; i <= n; i++) 
	{
		dis[i] = inf;
	}
	dis[s] = 0;
	for (int i = 1; i <= n; i++) 
	{
		int minn = inf, t = -1;
		for (int j = 1; j <= n; j++)
		{
			if (book[j] == 0 && minn > dis[j]) 
			{
				minn = dis[j];
				t = j;
			}
		}
		if (t == -1) break; 
		book[t] = 1;
		for (auto &e : G[t]) 
		{
			int v = e.to, w = e.val;
			if (dis[v] > dis[t] + w) 
			{
				dis[v] = dis[t] + w;
			}
		}
	}
	for (int i = 1; i <= n;i++) 
	{
		cout<< dis[i] << " ";
	}
	return 0;
}