#include<stdio.h>
#include<fstream.h>
int const pinfinit=36000;
int a[5][5],d[10],s[10],t[10],i,j,n,r,poz,min,k;
FILE *f;
void citire_graf()
{
	int x,y,z;
f=fopen("admitere.txt","r");
fscanf(f,"%d%d",&n,&k);

for(i=0;i<=n;i++)
	for(j=0;j<=n;j++)
		if(i!=j)
		a[i][j]=pinfinit;
		else
			a[i][j]=0;

for(i=0;i<k;i++)
	{
		fscanf(f,"%d%d%d",&x,&y,&z);
		a[x][y]=z;
		
	}

}
void drum(int i)
{
if (t[i]!=0) drum(t[i]);
printf(" %d ",i);
}
int main()
{
citire_graf();
printf("Introduceti nodul de pornire ");
scanf("%d",&r);
s[r]=1;
for(i=1;i<=n;i++)
	{
		d[i]=a[r][i];
		if(i!=r)
			if(d[i]<pinfinit) t[i]=r;
		
	}

for(i=1;i<=n-1;i++)
	{
		min=pinfinit;
		for(j=1;j<=n;j++)
			if(s[j]==0)
				if(d[j]<min)
					{
						min=d[j];
						poz=j;
					}
	s[poz]=1;
	for(j=1;j<=n;j++)
		if(s[j]==0)
			{
				if(d[j]>d[poz]+a[poz][j])
				{
					d[j]=d[poz]+a[poz][j];
					t[j]=poz;
				
				}
			}
	}
for(i=1;i<=n;i++)
	if(i!=r)
	if(t[i]!=0)
	{
		printf("distanta de la nodul %d la nodul %d este %d",r,i,d[i]);
		printf(":");
		drum(i);
		printf("\n");
	}
	/*
	else
		printf("Nu exista drum de la %d la %d",r,i);
	*/
return 0;
}