#include<bits/stdc++.h>
#define maxn 500005
#define MYINF -1
using namespace std;
class Seg {
public:
	int length, to;
	Seg* next;
	Seg(int to1, int length1) {
		next = NULL;
		length = length1;
		to = to1;
	}
};
class Node {
public:
	//	int count;
	Seg* head;
	Seg* tail;
	Node() {
		head = NULL;
		tail = NULL;
	}
	void addSeg(Seg* seg) {
		if (head == NULL) {
			head = seg;
			tail = seg;
		}
		else {
			tail->next = seg;
			tail = seg;
		}
	}
};
int bag[maxn];
bool inQue[maxn];
Node node[maxn];
int n, a, b, c, d;
int start, target;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;

//void shuRu1() {
//	ifstream ifstr("map2.txt");
//	ifstr >> n >> c >> start;
//	Seg* seg;
//	for (int i = 1; i <= c; i++) {
//		ifstr >> a >> b >> d;
//		if (a == b) {
//			continue;
//		}
//		seg = new Seg(b, d);
//		node[a].addSeg(seg);
//	}
//	ifstr.close();
//}
void shuRu2() {
	Seg* seg;
	cin >> n >> c >> start;
	for (int i = 1; i <= c; i++) {
		cin >> a >> b >> d;
		if (a == b) {
			continue;
		}
		else {
			seg = new Seg(b, d);
			node[a].addSeg(seg);
		}
	}
}
void bianli(int n) {
	if (node[n].head == NULL) {
		return;
	}
	Seg* seg = node[n].head;
	inQue[n] = 1;
	if (n == start) {
		do {
			a = seg->length;
			bag[seg->to] = a;
			que.push(make_pair(a, seg->to));
			seg = seg->next;
		} while (seg != NULL);
		return;
	}
	else {
		do {

			a = seg->length;
			if (bag[seg->to] == MYINF) {
				bag[seg->to] = bag[n] + a;
			}
			else {
				if (bag[n] + a < bag[seg->to]) {
					bag[seg->to] = bag[n] + a;
				}
			}
			if (!inQue[seg->to]) {
				que.push(make_pair(bag[seg->to], seg->to));
			}
			seg = seg->next;
		} while (seg != NULL);
	}




}
int main() {
	memset(bag, MYINF, sizeof(bag));
	shuRu2();
	//	shuRu1();
//	ofstream of("out.txt");
	bianli(start);
	bag[start] = 0;
	while (!que.empty())
	{
		if (!inQue[que.top().second]) {
			bianli(que.top().second);
		}
		que.pop();
	}
	for (int i = 1; i <= n; i++) {
		cout << bag[i] << " ";
		//			of<<"i:"<<i<<"::"<<bag[i]<<" ";
	}
	return 0;
}