#define int li

struct Edge {
  int to, cost;
};

void solve(__attribute__((unused)) bool read) {
  int n, m;
  cin >> n >> m;
  vector<vector<Edge>> g(n);
  for (int i = 0; i < m; ++i) {
    int a, b, cost;
    cin >> a >> b >> cost;
    --a; --b;
    g[a].push_back({b, cost});
    g[b].push_back({a, cost});
  }
  priority_queue<pair<int, int>> q;
  const int INF = (int)1e18;
  vector<int> dist(n, INF);
  dist[0] = 0;
  q.push({0, 0});
  vector<char> used(n, false);
  while (!q.empty()) {
    int v = q.top().second;
    q.pop();
    if (used[v]) {
      continue;
    }
    used[v] = true;
    for (auto e : g[v]) {
      int candy = e.cost + dist[v];
      if (candy < dist[e.to]) {
        dist[e.to] = candy;
        q.push({dist[e.to], e.to});
      }
    }
  }
  int res = dist[n - 1];
  if (res == INF) {
    res = -1;
  }
  cout << res << "\n";
}