let idx = 0;   //第几个
let size = 0;
let heap = [];
let posi_seq = [];    //posi_seq[位置] = 次序
let seq_posi = [];    //seq_posi[次序] = 位置


let insert = x => {
    heap[++size] = x;
    posi_seq[size] = ++idx;
    seq_posi[idx] = size;
    up(size);
}

let removeTop = () => {
    let top = heap[1];
    heap_swap(1, size--);
    down(1);
    return top;
}

let remove = k => {
    let position = seq_posi[k]
    heap_swap(position, size--);
    down(position);
    up(position);
}

let modify = (k, x) => {
    let position = seq_posi[k];
    heap[position] = x;
    down(position);
    up(position);
}

let down = x => {
    let u = x;
    if (2 * x <= size && heap[2 * x][1] < heap[u][1]) u = 2 * x;
    if (2 * x + 1 <= size && heap[2 * x + 1][1] < heap[u][1]) u = 2 * x + 1;
    if (u !== x) {
        heap_swap(x, u);
        down(u);
    }
}


let up = x => {
    let u = parseInt(x / 2);
    if (u && heap[u][1] > heap[x][1]) {
        heap_swap(u, x);
        up(u);
    }
}


let swap = (arr, i, j) => {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}


let heap_swap = (i, j) => {
    swap(posi_seq, i, j);
    swap(seq_posi, posi_seq[i], posi_seq[j]);
    swap(heap, i, j);

}


const INF = 0x3f3f3f3f;
const N = 150010;
//邻接表存储
let idx_1 = 1;
let e = [];
let next = [];
let w = new Int32Array(N).fill(INF);
let head = new Int32Array(N).fill(-1);

let dist = new Int32Array(N).fill(INF);
let isenter = new Int32Array(N);

let add = (a, b, c) => {
    e[idx_1] = b;
    next[idx_1] = head[a];
    w[idx_1] = c;
    head[a] = idx_1++;
}

let dijkstra = () => {
    insert([1, 0]);  //1号点，距离为0
    dist[1] = 0;
    while (size) {
        let top = removeTop();
        let point = top[0];
        if (isenter[point]) continue;
        isenter[point] = 1;
        for (let i = head[point]; i !== -1; i = next[i]) {
            let j = e[i];
            if (dist[j] > dist[point] + w[i]) {
                dist[j] = dist[point] + w[i];
                insert([j, dist[j]]);
            }
        }
    }
    if (dist[n] === INF) return -1;
    else return dist[n];

}



let n = 0, m = 0;

let buf = '';
process.stdin.on('readable', function () {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
    buf.split('\n').forEach(function (line, lineIdx) {
        if (lineIdx === 0) {
            n = getInputNums(line)[0];
            m = getInputNums(line)[1];
        } else if (lineIdx <= m) {
            let arr = getInputNums(line);
            let a = arr[0];
            let b = arr[1];
            let c = arr[2];
            add(a, b, c);
            if (lineIdx === m) {
                console.log(dijkstra());
            }
        }
    });
});