#include <functional>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

long long N, M;

typedef pair<long long, long long> Edge;
// Performance improvement - Static array and different neighbour vectors for bigger and smaller
pair<vector<Edge>, vector<Edge>> graph[100005] = { { vector<Edge>(), vector<Edge>() } };

// Performance improvement? - Edge& rather than Edge
typedef pair<Edge&, bool> Qedge;

long long dijkstra(long long s) {
	// Performance improvement - queue rather than priority_queue
	queue<Qedge> q;
	// Wrong answer on multiple tests - remove visited logic

	// Performance improvement - from vector to statis array
	// Wrong answer on a couple of tests - not init with { 0 }
	long long distlt[100005] = { 0 };
	long long distnlt[100005] = { 0 };
	distlt[s] = distnlt[s] = 0;
	Edge b = { 0, s };
	q.push({b, true});
	while (!q.empty()) {
		auto c = q.front().first;
		bool lt = q.front().second;
		q.pop();

		for (Edge& e : (lt) ? graph[c.second].second : graph[c.second].first) {
			if (e.second == 0 || e.second == c.second) continue;
			// cout << "From: " << c.second+1 << " To: " << e.second+1 << endl;
			long long (&dist)[100005] = (lt) ? distlt : distnlt;
			long long nd = ((!lt) ? distlt[c.second] : distnlt[c.second]) + e.first;
			if (dist[e.second] == 0 || nd < dist[e.second]) {
				dist[e.second] = nd;
				q.push({ e, !lt });
			}
			// cout << dist[e.second] << endl;
		}
	}
	if (distlt[N-1] == 0) return distnlt[N-1];
	if (distnlt[N-1] == 0) return distlt[N-1];
	return min(distlt[N-1], distnlt[N-1]);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (long long i = 0; i < M; i++) {
		long long ai, bi, di;
		cin >> ai >> bi >> di;
		ai--; bi--;
		if (ai > bi) {
			graph[ai].first.push_back({ di, bi });
			graph[bi].second.push_back({ di, ai });
		} else {
			graph[ai].second.push_back({ di, bi });
			graph[bi].first.push_back({ di, ai });
		}
	}

	// long long shortest = 1000000005;
	// dfs(0, 0, true, shortest);
	// cout << shortest << endl;
	cout << dijkstra(0) << endl;
}