#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  int ans[n + 1][n + 1];
  for (int t = 1; t <= n; t++)
    for (int p = 1; p <= n; p++) {
      if (t == p)
        ans[t][p] = 0;
      else
        ans[t][p] = 1000000000;
    }
  int aa, bb, k;
  for (int t = 0; t < m; t++) {
    cin >> aa >> bb >> k;
    ans[aa][bb] = k;
    ans[bb][aa] = k;
  }
  for (int t = 1; t <= n; t++) {
    for (int r = 1; r <= n; r++)
      for (int p = 1; p <= n; p++) {
        if (ans[p][r] > ans[p][t] + ans[t][r]) {
          ans[p][r] = ans[p][t] + ans[t][r];
          ans[r][p] = ans[p][t] + ans[t][r];
        }
      }
  }
  if (ans[1][n] < 1000000000)
    cout << ans[1][n];
  else
    cout << -1;
}
