#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

struct DATA{
    int u, last; 
	// u1 -> u -> u2
	// last > 0: tax[u] = cost[u1][u] = last
	// last < 0: tax[u] = cost[u][u2]
	ll cost;
	// last < 0: tax[u] haven't been added yet
	DATA(const int _u, const int _last, const ll _cost) {
		u = _u; last = _last; cost = _cost;
	}
	inline friend bool operator < (const DATA a, const DATA b) {
		return a.cost > b.cost;
	}
};

int n, m;
set<pii> a[100010], b[100010];
priority_queue<DATA> f;

int main() {
	// freopen("TAX.inp", "r", stdin);
	// freopen("TAX.out", "w", stdout);

	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		a[u].insert(make_pair(c, v)); a[v].insert(make_pair(c, u));
		b[u].insert(make_pair(-c, v)); b[v].insert(make_pair(-c, u));
	}
	for(set<pii>::iterator it = a[1].begin(); it != a[1].end();) {
		pii V = *it; it++;
		f.push(DATA(V.second, V.first, 2*V.first));
		a[1].erase(V); a[V.second].erase(make_pair(V.first, 1));
	}
	for(set<pii>::iterator it = b[1].begin(); it != b[1].end();) {
		pii V = *it; it++;
		f.push(DATA(V.second, V.first, -V.first));
		b[1].erase(V); b[V.second].erase(make_pair(V.first, 1));	
	}
	while (!f.empty()) {
		DATA t = f.top(); f.pop();
		if (t.u == n) {
			if (t.last > 0) {
				printf("%lld\n", t.cost);
				return 0;
			}
			continue;
		}		
		if (t.last > 0) {
			for(set<pii>::iterator it = a[t.u].begin(); it != a[t.u].end();) {
				pii V = *it; it++;
				if (t.last < V.first) break;
				f.push(DATA(V.second, V.first, t.cost+V.first));
				f.push(DATA(V.second, -V.first, t.cost));
				a[t.u].erase(V); a[V.second].erase(make_pair(V.first, t.u));
			}
		}
		if (t.last < 0) {
			for(set<pii>::iterator it = b[t.u].begin(); it != b[t.u].end();) {
				pii V = *it; it++;
				if (t.last < V.first) break;
				f.push(DATA(V.second, -V.first, t.cost-2*V.first));
				f.push(DATA(V.second, V.first, t.cost-V.first));
				b[t.u].erase(V); b[V.second].erase(make_pair(V.first, t.u));	
			}
		}
	}
	return 0;		
}