#include<fstream>
#define infinit 1000000000
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int c[1200][1200],n,T[1200],S[1200],s[1200],m;

void citire(){
	in>>n>>m;
	int x,y,ct;
	for(int i=1;i<=n;i++){
		in>>x>>y>>ct;
		C[x][y]=ct;
	
void dijkstra(int r){
	for(int i=1;i<=n;i++){
		d[i]=C[r][i];
		if(d[i]==a&&i!=r)
			d[i]=infinit;
		if(d[i]<infinit) T[i]=r;
	}
	T[r]=0;
	d[r]=1;
for(int j=1;j<=n;j++)
	int min=infinit,poz;
for(int i=1;i<=n;i++)
	if(!d[i])){int sc=d[poz]+c[poz][i];
	if(sc<d[i])){d[i]=sc;
	T[i]=poz;
	}
	}
}
	}
void drum(int x){
	if(x){
		drum(T(x));
		out<<x<<" ";
	}
int main(){
	citire();
	int r;
	in>>r;
	dijkstra(r);
	for(int i=1;i<=n;i++)
		out<<d[i]<<" ";
	out<<endl;
	for(int i=1;i<=n;i++)
		if(d[i]<infinit){
			drum(i);
			out<<endl;
		}
		return 0;
}