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

const long long INF = 1e18;

// Use dense Dijkstra (O(N^2)) instead of priority queue (O(M log N))
long long grid_matrix[5005][5005];
long long dist_matrix[5005];
bool visited_matrix[5005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            grid_matrix[i][j] = INF;
        }
        grid_matrix[i][i] = 0;
        dist_matrix[i] = INF;
        visited_matrix[i] = false;
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        if (w < grid_matrix[u][v]) {
            grid_matrix[u][v] = w;
            grid_matrix[v][u] = w;
        }
    }
    dist_matrix[1] = 0;
    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int i = 1; i <= n; i++) {
            if (!visited_matrix[i] && (u == -1 || dist_matrix[i] < dist_matrix[u])) {
                u = i;
            }
        }
        if (u == -1 || dist_matrix[u] == INF) break;
        visited_matrix[u] = true;
        for (int v = 1; v <= n; v++) {
            if (!visited_matrix[v] && grid_matrix[u][v] != INF) {
                if (dist_matrix[u] + grid_matrix[u][v] < dist_matrix[v]) {
                    dist_matrix[v] = dist_matrix[u] + grid_matrix[u][v];
                }
            }
        }
    }
    if (dist_matrix[n] == INF) cout << -1 << "\n";
    else cout << dist_matrix[n] << "\n";
    return 0;
}