#include<fstream.h>
#include<limits.h>
#define NM 100
#define INF (INT_MAX-10)/2

int c[NM][NM], d[NM],s[NM], prec[NM],n,start=1,m;
ifstream fin("dijstra.in");
ofstream fout("dijstra.out");

void build(){
fin>>n>>m;
int x,y,i,cost,j;
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
    c[i][j]=INF;
for(i=1;i<=n;i++)
   c[i][j]=0;
for(i=1;i<=m;i++){
    fin>>x>>y>>cost;
    c[x][y]=cost;
    }
fin>>start;
    }

void init(){
int i;
s[start]=1;
for(i=1;i<=n;i++){
   d[i]=c[start][i];
   if(d[i]<INF && i!=start)
      prec[i]=start;
      }
     }

int minim(){

int m=INF*2,i,k;
for(i=1;i<=n;i++)
  if(!s[i]&&d[i]<m){
     m=d[i];
     k=i;
     }
  return k;
  }

void dijstra(){
int k,i,dc,nrs=1,gata=0;
do{ k=minim();
  if(d[k]==INF||nrs==n)
     gata=1;
  else { s[k]=1;
	nrs++;
  for(i=1;i<=n;i++)
  if(!s[i]){
    dc=d[k]+c[k][i];
    if(dc<d[i]){
	d[i]=dc;
	prec[i]=k;
	  }
	    }
	      }
    }
    while(!gata);
     }

void drum(int x){
if(x){
 drum(prec[x]);
   cout<<x<<" ";
     }
       }

int main(){
int i;
build();
dijstra();
for(i=1;i<=n;i++)
  fout<<d[i]<<" ";
  fout<<endl;
for(i=1;i<=n;i++)
  if(s[i]){
    fout<<"drumul pana la "<<i<<" este in: ";
drum(i);
fout<<endl;
}
else
fout<<"Nu exista drum la nodul"<<i<<endl;
return 0;
}