#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int dis[10010];
int n,m,s;
struct node{
	int x,to,val; 
};
node gra[10010];
bool bf(int s)
{
	bool flag;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	for(int p=1;p<n;p++)
		for(int i=1;i<=m;i++)
		{
			if(dis[gra[i].to]>dis[gra[p].x]+gra[p].val)
				dis[gra[i].to]=dis[gra[p].x]+gra[p].val;
		}
}
int main()
{
	cin>>n>>m>>s;
	for(int p=1,x,y,z;p<=m;p++)
		cin>>gra[p].x>>gra[p].to>>gra[p].val;
	bf(s);
	for(int p=1;p<=n;p++)
		cout<<dis[p]<<' ';
}

求助QAQ