#include<fstream>

using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
#define infinit 1000000000
int n,c[1200][1200],t[1200],s[1200],d[1200],m;
void citire(){
	int x,y,ct;
	in>>n>>m;
	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]<infinit) t[i]=r;
	 }
	 t[r]=0;
	 s[r]=1;
	 int min=infinit,poz;
	 for(int j=1;j<=n;j++)
		  
	 for(int i=1;i<=n;i++)
		 if(!s[i])
			 if(d[i]<min){ poz=i;
		                   min=d[i];
			 }
			s[poz]=i;
for(int i=1;i<=n;i++)
 if(!s[i]){ int sc=d[poz]+c[poz][i];
if(sc<d[i]){ s[i]=sc;
             t[i]=poz;
}
 }
}
 int main(){
	 int r;
	 citire();
	 in>>r;
	 dijkstra(r);
 }