#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const long long inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int ctz(int x) { return __builtin_ctz(x); }
int clz(int x) { return __builtin_clz(x); }
const int maxn = 1e5 + 5;
vector<pair<int, int>> g[maxn];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> edg;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    edg.emplace_back(u, v, w);
  }
  sort(edg.begin(), edg.end());
  for (int i = 0; i < m; i++) {
    int u, v, w;
    tie(u, v, w) = edg[i];
    auto l = lower_bound(edg.begin(), edg.end(), make_tuple(u + 1, 0, 0));
    auto r = lower_bound(edg.begin(), edg.end(), make_tuple(v, 0, 0));
    if (l == edg.end()) l--;
    if (r == edg.end()) r--;
    int x11, x21, x31, y11, y21, y31;
    tie(x11, x21, x31) = *l;
    tie(y11, y21, y31) = *r;
    if (x11 > u) {
      l--;
    }
    if (y11 > v) {
      r--;
    }
    int x1, x2, x3, y1, y2, y3;
    tie(x1, x2, x3) = *l;
    tie(y1, y2, y3) = *r;
    g[u].emplace_back(x1, w);
    g[x1].emplace_back(u, w);
    g[u].emplace_back(y1, w);
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
    g[y1].emplace_back(u, w);
  }
  vector<long long> dist(n + 1, inf);
  priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                 greater<pair<long long, int>>>
      pq;
  pq.emplace(0, 1);
  dist[1] = 0;
  while (!pq.empty()) {
    int w, u;
    tie(w, u) = pq.top();
    pq.pop();
    if (u == n) return cout << w, 0;
    for (int i = 0; i < g[u].size(); i++) {
      int v, d;
      tie(v, d) = g[u][i];
      if (dist[v] > dist[u] + d) {
        dist[v] = dist[u] + d;
        pq.emplace(dist[v], v);
      }
    }
  }
  cout << -1;
}
