#include<fstream.h>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
define infinit 1000000000

int C[1200][1200],n,T[1200],S[1200],d[1200],m;

void citire(){
in>>n>>m;
for(int i=1;i<=n;i++)
	for(int j=1;j<=n;i++)
		if(i!=j)
			C[i][j]=infinit;
for(int i=1;i<=m;i++){
	int x,y,ct;
	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]<infinit) T[i]=r;
}
T[r]=0;
S[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;
}