#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 510;
const int M = 1e5 + 10;
int n, m;

//邻接表
int h[N], w[M], e[M], ne[M], idx;
bool st[N];  //是否使用过
int dist[N]; //最短距离数组

//维护邻接表
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist); //初始化为无穷大
    dist[1] = 0;                     //出发点的距离初始化为0

    for (int i = 0; i < n; i++) {
        //找到距离出发点最近的点
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;
        for (int j = h[t]; ~j; j = ne[j]) {
            int k = e[j];
            dist[k] = min(dist[k], dist[t] + w[j]);
        }
    }
    return dist[n] == INF ? -1 : dist[n];
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    //调用迪卡斯彻算法
    int t = dijkstra();
    printf("%d\n", t);
    return 0;
}