#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<ctime>
#define int long long
using namespace std;
const int N = 100010, M = 200010;
int n, m, s, u, v, w, dis[N];//dis[i]是从起点到i的最短路
int x, vl[M], son[M][2], sz[M], pos[M], root, a, b, c, cnt;
bool vis[N];//判断是否进队
struct fhq_treap {
	int wei[M], tot;
	int update(int x,int o)
	{
		++tot;
		vl[tot] = x;
		pos[tot] = o;
		wei[tot] = rand();
		sz[tot] = 1;
		return tot;
	}
	void push(int x)
	{
		sz[x] = 1 + sz[son[x][0]] + sz[son[x][1]];
	}
	void split(int x, int k, int& a, int& b)
	{
		if (!x) a = b = 0;
		else
		{
			if (vl[x] <= k)
			{
				a = x;
				split(son[x][1], k, son[x][1], b);
			}
			else
			{
				b = x;
				split(son[x][0], k, a, son[x][0]);
			}
			push(x);
		}
	}
	int merge(int a, int b)
	{
		if (!a || !b) return a + b;
		if (wei[a] < wei[b])
		{
			son[a][1] = merge(son[a][1], b);
			push(a);
			return a;
		}
		else
		{
			son[b][0] = merge(a, son[b][0]);
			push(b);
			return b;
		}
	}
	int find(int x, int k)
	{
		while (1)
		{
			if (k <= sz[son[x][0]])
				x = son[x][0];
			else if (k == sz[son[x][0]] + 1)
				return x;
			else
			{
				k -= sz[son[x][0]] + 1;
				x = son[x][1];
			}
		}
	}
}T;
struct Graph {
	int hd[N], vr[M], wl[M], nxt[M], tot = 0, o;
	void add(int u, int v, int w)//前向星存图
	{
		++tot;
		vr[tot] = v;
		wl[tot] = w;
		nxt[tot] = hd[u];
		hd[u] = tot;
	}
	void dijkstra(int s)
	{
		int x = 0, p = s;
		T.split(root, x, a, b);
		root = T.merge(T.merge(a, T.update(x, p)), b);
		++cnt;
		while (cnt)
		{
			x = vl[T.find(root, 1)];
			p = pos[T.find(root, 1)];
			T.split(root, x, a, c);
			T.split(a, x - 1, a, b);
			b = T.merge(son[b][0], son[b][1]);
			root = T.merge(T.merge(a, b), c);
			--cnt;
			if (vis[p]) continue;
			vis[p] = 1;
			for (int i = hd[p]; i; i = nxt[i])
			{
				if (dis[p] + wl[i] < dis[vr[i]])
				{
					dis[vr[i]] = dis[p] + wl[i];
					if (!vis[vr[i]])
					{
						++cnt;
						T.split(root, dis[vr[i]], a, b);
						root = T.merge(T.merge(a, T.update(dis[vr[i]], vr[i])), b);
					}
				}
			}
		}
	}
}G;
signed main()
{
	srand((unsigned)time(NULL));
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	cin >> n >> m >> s;
	for (int i = 1; i <= m; ++i)
	{
		cin >> u >> v >> w;
		G.add(u, v, w);
	}
	dis[s] = 0;
	G.dijkstra(s);
	for (int i = 1; i <= n; ++i)
	{
		cout << dis[i] << ' ';
	}
	return 0;
}