——所以我们可以尝试动态加边啦~

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define mod 1000000007
#define ll long long
#define M 210005
#define N 50005
#define inf (1 << 29)
struct IN{
int x, y, a, b;
friend inline bool operator < (IN const &x, IN const &y)
{
return x.a < y.a;
}
}in[M >> 1];
struct edge{
int to, nxt, b;
}e[M];
int n, m, tot, d[N], head[N], ans = inf;
struct node{
int d, pos;
friend inline bool operator < (const node &x, const node &y)
{
return x.d > y.d;
}
};
std::priority_queue <node> q;
inline void addedge (int u, int v, int b)
{
e[++tot] = (edge) {v, head[u], b};
e[++tot] = (edge) {u, head[v], b};
}
inline void spfa ()
{
while (!q.empty())
{
node u = q.top(); q.pop();
while (u.d != d[u.pos] && !q.empty())
{
u = q.top();
q.pop();
}
if (q.empty() && u.d != d[u.pos]) break;
for (int i = head[u.pos]; i; i = e[i].nxt)
{
int v = e[i].to;
if (std::max(d[u.pos], e[i].b) < d[v])
{
d[v] = std::max(d[u.pos], e[i].b);
q.push((node) {d[v], v});
}
}
}
}
int main ()
{
scanf("%d %d", &n, &m);
fo (i, 1, m)
scanf("%d %d %d %d", &in[i].x, &in[i].y, &in[i].a, &in[i].b);
std::sort(in + 1, in + m + 1);
fo (i, 2, n) d[i] = inf;
fo (i, 1, m)
{
int u = in[i].x, v = in[i].y;
if (d[u] > d[v]) std::swap(u, v);
if (std::max(d[u], in[i].b) < d[v])
{
d[v] = std::max(d[u], in[i].b);
q.push((node) {d[v], v});
spfa();
}
ans = std::min(ans, d[n] + in[i].a);
}
if (ans == inf)
printf("-1");
else
printf("%d", ans);
return 0;
}