#include<fstream>
using namespace std;
ifstream intrare("bellmanford.in");
ofstream iesire("bellmanford.out");
long int cmin[50001],tata[50001],Cost[5001][5001],x,y,m,n,cost,start,p,vfmin;
int minim(int cmin[])
{
	int i,mini;
	mini=cmin[1]; 
	for(i=2;i<=n;i++)
		if(cmin[i]>mini)
			mini=cmin[i];
	return mini;
}	
int main()
{
	int i,j,schimb;
	intrare>>n>>m>>start;
	for(i=1;i<=m;i++)
	{
		intrare>>x>>y>>cost;
		Cost[x][y]=cost;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j && Cost[i][j]==0)
				Cost[i][j]=50001*50001;	
	for(i=1;i<=n;i++)
		cmin[i]=Cost[start][i];
	cmin[start]=0;
	for(i=1;i<=n;i++)
		tata[i]=start;
	tata[start]=0;
	p=n;
	while(p)
	{
		schimb=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(cmin[j]>cmin[i]+Cost[i][i])
				{
					cmin[j]=cmin[i]+Cost[i][j];
					tata[j]=i;
					schimb++;
				}
		p--;
	}
	if(schimb!=0)
		iesire<<"Nu exista solutii"<<'\n';
	else
		for(i=1;i<=n;i++)
			iesire<<"Drumul minim de la "<<start<<" la "<<i<<" este : "<<cmin[i];
	iesire.close();
	return 0;
}