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

4
typedef pair<int, int> PII;
5

6
const int N = 150010;
7
const int M = 150010;
8
const int INF = 0x3f3f3f3f;
9

10
int n, m;
11
int h[N], e[M], w[M], ne[M], idx;
12
int dista[N];
13
bool st[N];
14

15
void add(int a, int b, int c) {
16
    e[idx] = b;
17
    w[idx] = c;
18
    ne[idx] = h[a];
19
    h[a] = idx++;
20
}
21

22
int dijkstra() {
23
    memset(dista, 0x3f, sizeof dista);
24

25
    priority_queue<PII, vector<PII>, greater<PII>> heap;
26

27
    dista[1] = 0;
28
    heap.push({0, 1});
29

30
    while (!heap.empty()) {
31
        auto t = heap.top();
32
        heap.pop();
33

34
        int distance = t.first;
35
        int ver = t.second;
36

37
        if (st[ver]) continue;
38
        st[ver] = true;
39

40
        for (int i = h[ver]; i != -1; i = ne[i]) {
41
            int j = e[i];
42

43
            if (dista[j] > distance + w[i]) {
44
                dista[j] = distance + w[i];
45
                heap.push({dista[j], j});
46
            }
47
        }
48
    }
49

50
    if (dista[n] == INF) return -1;
51
    return dista[n];
52
}
53

54
int main() {
55
    scanf("%d%d", &n, &m);
56
    memset(h, -1, sizeof h);
57

58
    while (m--) {
59
        int a, b, c;
60
        scanf("%d%d%d", &a, &b, &c);
61
        add(a, b, c);
62
    }
63

64
    printf("%d\n", dijkstra());
65
    return 0;
66
}