#include<iostream>
using namespace std;
int u[10000+1],v[10000+1],w[10000+1],cost[10000+1];
int main()
{ 
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;i++)
		{
			if(cost[v[j]]>cost[u[j]]+w[j])
				cost[v[j]]=cost[u[j]]+w[j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<cost[i]<<" ";
	}
	return 0;
}