// Arup Guha
// 12/17/2019
// Solution to 2014 February USACO Silver Problem: Roadblock

import java.util.*;
import java.io.*;

public class rblock {
	
	public static int n;
	public static ArrayList[] g;
	
	public static int[] dist;
	public static int[] path;
	
	public static void main(String[] args) throws Exception {
		
		// Read in the basic graph parameters.
		BufferedReader stdin = new BufferedReader(new FileReader("rblock.in"));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		n = Integer.parseInt(tok.nextToken());
		int numE = Integer.parseInt(tok.nextToken());
		g = new ArrayList[n];
		for (int i=0; i<n; i++) g[i] = new ArrayList<edge>();
		
		// Add the edges.
		for (int i=0; i<numE; i++) {
			tok = new StringTokenizer(stdin.readLine());
			int u = Integer.parseInt(tok.nextToken())-1;
			int v = Integer.parseInt(tok.nextToken())-1;
			int w = Integer.parseInt(tok.nextToken());
			g[u].add(new edge(u, v, w));
			g[v].add(new edge(v, u, w));
		}
		
		// Get all shortest distances from vertex 0, keeping paths. Store best to n-1.
		dijkstras(0,true);
		int best = dist[n-1], res = 0;
		
		// Peel back path.
		int last = n-1;
		while (path[last] != last) {
			
			// Double this edge weight.
			int prev = path[last];
			adjustWeight(prev, last, true);
			
			// Rerun Dijkstra's getting the new best weight.
			dijkstras(0,false);
			
			// See how much worse this makes it.
			res = Math.max(res, dist[n-1]-best);
			
			// Put this back to the original (div by 2).
			adjustWeight(prev, last, false);
			
			// Uupate to previous edge.
			last = path[last];
		}
		

		// Output to file.
		PrintWriter out = new PrintWriter(new FileWriter("rblock.out"));
		out.println(res);
		out.close();		
		stdin.close();
	}
	
	// Doubles the edge from start to end if doubleIt is true, halves it otherwise.
	public static void adjustWeight(int start, int end, boolean doubleIt) {
		
		// Find the edge and double or halve it.
		for (edge e: (ArrayList<edge>)g[start])
			if (e.v == end)
				e.w = doubleIt ? 2*e.w : e.w/2;
			
		// Same for hte edge going back the other way.
		for (edge e: (ArrayList<edge>)g[end])
			if (e.v == start)
				e.w = doubleIt ? 2*e.w : e.w/2;
	}
	
	public static void dijkstras(int source, boolean doPath) {
		
		// Lots of set up for dijkstras.
		dist = new int[n];
		Arrays.fill(dist, -1);
		dist[source] = 0;
		if (doPath) {
			path = new int[n];
			Arrays.fill(path, -1);
			path[source] = source;
		}
		
		// Add in all edges from source.
		PriorityQueue<edge> pq = new PriorityQueue<edge>();
		for (edge e: (ArrayList<edge>)g[source]) pq.offer(e);
		
		// Run till done.
		while (pq.size() > 0) {
			
			// Get next best.
			edge cur = pq.poll();
			if (dist[cur.v] != -1) continue;
			
			// If we get here this is a shortest distance.
			dist[cur.v] = cur.w;
			if (doPath) path[cur.v] = cur.u;
			
			// Enqueue all new paths not to known places.
			for (edge e: (ArrayList<edge>)g[cur.v]) 
				if (dist[e.v] == -1) 
					pq.offer(new edge(e.u, e.v, cur.w+e.w));
		}
	}
}

class edge implements Comparable<edge> {

	public int u;
	public int v;
	public int w;
	
	public edge(int from, int to, int weight) {
		u = from;
		v = to;
		w = weight;
	}
	
	public int compareTo(edge other) {
		return w - other.w;
	}	
}