#include <fstream>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> pi;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int INF = 1e9 + 1;
const int MARIME = 100005;

int n, m, start, dist[MARIME];
bool in_coada[MARIME];

struct cmp {
	bool operator()(int a, int b) { return dist[a] > dist[b]; }
};

priority_queue<int, vector<int>, cmp> pq;
vector<pi> graf[MARIME];

int main() {
	// citire si pregatire
	fin >> n >> m >> start;
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	dist[start] = 0;
	pq.push(start);
	in_coada[start] = true;
	for (int i = 1; i <= m; i++) {
		int x, y, d;
		fin >> x >> y >> d;
		graf[x].push_back(make_pair(y, d));
		// graf[y].push_back(make_pair(x, d));
	}
	// dijkstra
	while (!pq.empty()) {
		int nod = pq.top();
		int cost_nod = dist[nod];
		pq.pop();
		in_coada[nod] = false;
		for (auto& x : graf[nod]) {
			int vecin = x.first;
			int cost_vecin = cost_nod + x.second;
			if (cost_vecin >= dist[vecin]) {
				continue;
			}
			dist[vecin] = cost_vecin;
			if (in_coada[vecin]) {
				continue;
			}
			pq.push(vecin);
			in_coada[vecin] = true;
		}
	}
	// afisare
	for (int i = 1; i <= n; i++) {
		fout << (dist[i] == INF ? -1 : dist[i]) << ' ';
	}
	return 0;
}