#include<bits/stdc++.h>
using namespace std;
//#define m( make_pair(
int nxt[100010],h[100010],z[100010],w[100010],d[100010],zz=0;
bool f[100010];
//priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >s;
struct nd {
	int a;
	int b;
	bool operator < (const nd &ndt)const {
		return ndt.a < a;
	}
//     bool operator ()(nd &x,nd &y){
//    return x.a>y.a;//小根堆重载

};
priority_queue<nd>s;
void add(int a,int b,int c) {
	zz++;
	nxt[zz]=h[a];
	h[a]=zz;
	z[zz]=b;
	w[zz]=c;
}
int main() {
	int n,m,st,i,j,minn=0x7f7f7f7f;
	cin>>n>>m>>st;
	memset(nxt,-1,sizeof(nxt));
	for(i=1; i<=m; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	memset(d,0x3f,sizeof(d));
	int wz;
	d[st]=0;
	s.push((nd) {
		d[st],st
	});
//	cout<<s.top()<<" ";
	int wzz;
	while(!s.empty()) {
		nd op=s.top();
		wz=op.b;
		wzz=op.a;
		s.pop();;
		if(f[wz])continue;
		f[wz]=1;
		for(j=h[wz]; j!=-1; j=nxt[j]) {
			if(d[z[j]]>wzz+w[j]) {
				d[z[j]]=wzz+w[j];
				if(!f[wz])
					s.push((nd) {
					d[z[j]],z[j]
				});
			}

		}

	}
	for(i=1; i<=n; i++) {
		cout<<d[i]<<" ";
	}
	return 0;
}