#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 5010;

vector < pair <int, int> > g[N];

int n, m;
int a[N][N];
int dis[N][2];
bool vis[N];

void dijkstra () {
	for (int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = INF;
	dis[n][0] = 0;
	for (int i = 1; i <= n; i++) {
		int minn = INF, minj;
		for (int j = 1; j <= n; j++)
			if (!vis[j] and dis[j][0] < minn) {
				minn = dis[j][0];
				minj = j;
			}
		vis[minj] = 1;
		for (int j = 0; j < g[minj].size(); j++) {
			int v = g[minj][j].first;
			int c = g[minj][j].second;
			if (dis[v][0] > dis[minj][0] + c) {
				dis[v][1] = dis[v][0];
				dis[v][0] = dis[minj][0] + c;
				if (dis[v][1] > dis[minj][1] + c)
					dis[v][1] = dis[minj][1] + c;
			} else if (dis[v][1] > dis[minj][0] + c)
				dis[v][1] = dis[minj][0] + c;
		}
			
	}
}

int main () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		g[u].push_back (make_pair (v, c));
		g[v].push_back (make_pair (u, c));
	}
	dijkstra ();
	if (dis[1][1] == INF) cout << -1;
	else cout << dis[1][1];
	return 0;
}