#include<bits/stdc++.h>
using namespace std;

typedef int itn;
typedef long long ll;
typedef pair<int, int> P;
const int MAX = 100005;

struct edge {
	int to;
	int cost;
};
vector<edge>a[MAX];
int d[MAX];
int vis[MAX];
set<P>s;//first:点编号  second:最短距离
void Dijkstra(int p) {
	s.insert(P(p, 0));
	while (s.size()) {
		int v = s.begin()->first;
		int dis = s.begin()->second;
		s.erase(s.begin());
		if (dis > d[v])continue;
		for (int i = 0; i < a[v].size(); i++) {
			edge e = a[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				
				s.insert(P(e.to, d[e.to]));
			}
		}
	}
}
int main() {
	int n, m, p;
	cin >> n >> m >> p;
	for (int i = 0; i < m; i++) {
		int from; 
		cin >> from;
		edge e;
		cin >> e.to >> e.cost;
		a[from].push_back(e);
	}
	memset(d, 0x3f, sizeof(d));
	d[p] = 0;
	Dijkstra(p);
	for (int i = 1; i <= n; i++)
	{
		cout << d[i] << " ";
	}
	return 0;
}