#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int f[5010][5010];//再大就MLE了,实在开不了
int d[10010];
bool v[10010];
int qm(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
void dijkstra()
{
	for(int i=1;i<=n;++i)
	{
		d[i]=2147483647;
		v[i]=0;
	}
	d[1]=0;
	for(int i=1;i<n;++i)
	{
		int x=0;
		for(int j=1;j<=n;++j)
		{
			if(!v[j]&&(x==0||d[x]>d[j]))
			{
				x=j;
			}
		}
		v[x]=true;
		for(int y=1;y<=n;++y)
		{
			if(f[x][y]!=-1)
				d[y]=qm(d[y],d[x]+f[x][y]);
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)
	{
		f[i][i]=0;
	}
	for(int i=1;i<=m;++i)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(a<s)
			a=a+n-s+1;
		else
			a=a-s+1;
		if(b<s)
			b=b+n-s+1;
		else
			b=b-s+1;
		f[a][b]=c;
	}
	dijkstra();
	for(int i=1;i<=n;++i)
	{
		if(d[i]==0x3f)
			d[i]=2147483647;
		cout<<d[i]<<" ";
	}
	return 0;
}