#include <cstdio>
using namespace std;


int n,m,x,y,cmin[100],i,j,z,tata[100],c[100][100],st,M[100],min,vfmin,gr[100][100];

int main()
{
	FILE* f=fopen("roy.in","r");
	FILE* g=fopen("roy.out","w");
	fscanf(f,"%d %d %d",&n,&m,&st);
	
	for (i=0;i<=n;i++)
		for (j=0;j<=n;j++)
			c[i][j]=cmin[i]=999999;
		
	for (i=0;i<m;i++)
	{
		fscanf(f,"%d %d %d",&x,&y,&z);
		c[x][y]=gr[x][y]=z;
	}
	
	
	
	for (i=1;i<=n;i++)
		if (c[st][i])
			cmin[i]=c[st][i];
	M[st]=1;
	int ok;
	for (i=0;i<n;i++)
	{
		ok=1;
		for (x=1;x<=n;x++)
			for (y=1;y<=n;y++)
			{
				if (c[x][y])
				{
					if (cmin[y]>cmin[x]+c[x][y])
					{
						cmin[y]=cmin[x]+c[x][y];
						ok=0;
					}
				}
			}
	}
	
	if (ok)
	{
		for (i=1;i<=n;i++)
		{
			fprintf(g,"%d ",st,i,cmin[i]);
		}
	}
	
	fclose(f);
	fclose(g);
	return 0;
}