#include <fstream.h>
#include <vector>

using namespace std;
int n,m,s,d[50000],u[50000];
const long inf = 100000000;

ifstream fi("dijkstravect.in");
ofstream fo("dijkstravect.out");
vector<vector<pair<int,int> > >v;

void citire(){
	fi>>n;
	fi>>m;
	fi>>s;
	v.resize(n+1);
	int i,j,k,c;
	for(i=1;i<=n;i++)
		v[i].push_back(pair<int,int>(0,0));
	for(k=1;k<=m;k++){
		fi>>i;
		fi>>j;
		fi>>c;
		v[i].push_back(pair<int,int>(j,c));
		v[i][0].first++;
	}
	fi.close();
}

void afisare(){
	int i;
	for(i=2;i<=n;i++)
		fo<<d[i]<<" ";
	fo<<'\n';
	fo.close();
}

void dijkstra(){
	long min;
	int i,nod;
	for(i=2;i<=n;i++)
		d[i]=inf;
	u[1]=1;
	for(i=1;i<=v[1][0].first;i++)
		d[v[1][i].first]=v[1][i].second;
	
	while(1){
		min=inf;
		nod = -1;
		for(i=1;i<=n;i++)
			if(!u[i] && min>d[i]){
				min=d[i];
				nod=i;
			}
		
		u[nod]=1;
		if(min==inf)
			break;
		
		for(i=1;i<=v[nod][0].first;i++)
			if(d[v[nod][i].first]>d[nod]+v[nod][i].second)
				d[v[nod][i].first]=d[nod]+v[nod][i].second;
	}
}	

int main(){
	citire();
	dijkstra();
	afisare();
	return 0;
}