// editor3
#include<stdio.h>
#define max 20
int graph[max][max];
int visited[max];
int n;
int w;
int mincost;
int des;
void dfs(int v,int des,int w){
    if(v==des){
        if(w<mincost){
            mincost=w;
        }
        return;
    }
    visited[v]=1;
    for(int i=1;i<=n;i++){
        if(graph[v][i]!=0 && !visited[i]){
            dfs(i,des,w);
        }
    }
    visited[v];
}
int main(){
    int m,des;
    scanf("%d %d",&n,&m);
    if(n<0 || m<0){
        printf("Invalid input");
        return 0;
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            graph[i][j]=0;
        }
    }
    int v,e;
    for(int i=0;i<=m;i++){
        scanf("%d %d %d",&v,&e,&w);
        graph[v][e]=w;
       
    }
   int start=1,des=5;
   dfs(start,des,0);
   printf("%d\n",mincost);
   
return 0;
}