1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef __gnu_pbds::cc_hash_table<int, int> HashMap;
char ch;
bool iosig;
template<class T>
inline void read(T &x) {
x = 0, iosig = 0;
do {
ch = getchar();
if (ch == '-') iosig = 1;
} while (!isdigit(ch));
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
}
const int MAX = 6000000;
int n, m;
struct Data {
int l, r, w;
inline bool operator < (const Data &n) const {
return l > n.l;
}
} data[MAX];
struct Node {
int v, w;
Node(int v, int w) : v(v), w(w) {}
inline bool operator < (const Node &n) const {
return w > n.w;
}
};
vector<Node> edge[MAX];
inline void addEdge(int u, int v, int w) {
edge[u].push_back(Node(v, w));
}
long long dis[MAX];
bool vis[MAX];
HashMap h;
struct Query {
int v;
long long w;
Query(int v, long long w) : v(v), w(w) {}
inline bool operator < (const Query &n) const {
return w > n.w;
}
};
typedef __gnu_pbds::priority_queue<Query> Heap;
Heap::point_iterator id[MAX];
int len;
int ranges[MAX];
inline void dijkstra(int s) {
Heap q;
fill(dis + 1, dis + len + 1, LONG_LONG_MAX);
dis[s] = 0;
id[s] = q.push(Query(s, 0));
while (!q.empty()) {
register int now = q.top().v;
q.pop();
if (vis[now]) continue;
vis[now] = true;
for (register int i = 0; i < edge[now].size(); i++) {
Node *it = &edge[now][i];
if (it->w + dis[now] < dis[it->v]) {
dis[it->v] = it->w + dis[now];
if (id[it->v] != NULL) q.modify(id[it->v], Query(it->v, dis[it->v]));
else id[it->v] = q.push(Query(it->v, dis[it->v]));
}
}
}
}
int main() {
read(n), read(m);
for (register int i = 1; i <= m; i++)
read(data[i].l), read(data[i].r), read(data[i].w), ranges[(i << 1) - 1] = data[i].l, ranges[i << 1] = data[i].r;
sort(data + 1, data + m + 1);
sort(ranges + 1, ranges + (m << 1 | 1));
len = unique(ranges + 1, ranges + m * 2 + 1) - (ranges + 1);
if (ranges[1] != 1 || ranges[len] != n)
cout << "-1", exit(0);
for (register int i = len; i > 1; i--)
addEdge(i, i - 1, 0);
for (register int i = 1; i <= len; i++)
h[ranges[i]] = i;
for (register int i = 1; i <= m; i++) {
data[i].l = h[data[i].l], data[i].r = h[data[i].r];
if (data[i].l > data[i].r) swap(data[i].l, data[i].r);
addEdge(data[i].l, data[i].r, data[i].w);
}
dijkstra(1);
cout << (dis[len] == LONG_LONG_MAX ? -1 : dis[len]);
return 0;
}
|
