#include <iostream>
#include <cstring>
#include <limits>
#include <climits>
using namespace std;
int cost = 0;
template<int M, int N>
int findNext(int next,int visited[],int adjMatrix[M][N]){
int node, minIndex, tempCost, minimum = INT_MAX;
for(int i=0; i<N; i++){
if(!visited[i] && adjMatrix[next][i]!=0 && adjMatrix[next][i]<minimum){
tempCost = cost+adjMatrix[next][i];
minimum = adjMatrix[next][i] ;
minIndex = i;
}
}
node = minIndex;
cost = cost+tempCost;
return node;
}
template<int X, int Y>
void Tsm(int start,int visited[],int adjMatrix[X][Y]){
int next;
visited[start] = 1;
cout<<"Path : ";
next = findNext(start,visited,adjMatrix);
if(next == INT_MAX){
int value = 0;
cost = cost+adjMatrix[next][value];
cout<<value;
return;
}
Tsm(next,visited,adjMatrix);
}
int main() {
int N,E,start;
cin>>N>>E;
int adjMatrix[N][N];
memset(adjMatrix,0,sizeof(adjMatrix));
for(int i=0; i<E; i++ )
{
int u,v,w;
cin>>u>>v>>w;
adjMatrix[u][v]=w;
}
int visited[N];
for(int i=0; i<N; i++){
visited[i]=0;
}
cout<<"Enter start node: ";
cin>>start;
Tsm(start,visited,adjMatrix);
return 0;
}