Untitled

import java.io.*;
import java.util.*;
public class Main {
 
static HashMap<Integer,ArrayList<Node>> adjList = new HashMap<>();
static HashMap<Integer,ArrayList<Node>> adjList2 = new HashMap<>();


static class Node{
    public int to;
    public long weight;
    public Node(int to, long weight){
    this.to = to;
    this.weight = weight;
    }


    public long getWeight(){
    return this.weight;
    }
}




public static void main(String[] args) throws IOException{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    String[] s=br.readLine().trim().split(" ");
    int nodes =Integer.parseInt(s[0]);
    int edges =Integer.parseInt(s[1]);
    for(int i = 1; i <= nodes ; i++){
    adjList.put(i,new ArrayList<Node>());
    adjList2.put(i,new ArrayList<Node>());}
    for(int i = 0 ; i < edges ; i++){
    s=br.readLine().trim().split(" ");
    int source = Integer.parseInt(s[0]);
    int d = Integer.parseInt(s[1]);
    long w = Long.parseLong(s[2]);
    adjList.get(source).add(new Node(d,w));
    adjList2.get(d).add(new Node(source,w));
    }
    long[] sorceDijktra = Dijkstra(adjList,1,nodes);
    long[] desDijkstra=Dijkstra(adjList2,nodes,nodes);
    long ans=Long.MAX_VALUE;
    for(int i=1;i<=nodes;i++){
    for(Node it:adjList.get(i)){
    long res=(long)((sorceDijktra[i]+desDijkstra[it.to])+it.weight/2);
    ans=Math.min(ans,res);}
    }
    bw.write(ans+"");
    bw.flush();
}




public static long[] Dijkstra(HashMap<Integer,ArrayList<Node>> adjList,int src, int nodes){
    boolean[] visited = new boolean[nodes+1];
    long[] distance = new long[nodes+1];
    Arrays.fill(distance,Integer.MAX_VALUE);
    Comparator<Node> NodeComparator= Comparator.comparingLong(Node::getWeight);
    PriorityQueue<Node> qu = new PriorityQueue<>(NodeComparator);
    qu.add(new Node(src,0));
    while(!qu.isEmpty()){
    Node source = qu.remove();
    if(visited[source.to])
    continue;
    visited[source.to] = true;
    distance[source.to]=source.getWeight();
    for(Node neighbour : adjList.get(source.to)){
    qu.add(new Node(neighbour.to,source.getWeight()+neighbour.getWeight()));


    }
    }
    return distance;
    }
}