#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Edge {
ll a, b, c, d;
};
ll M = 210, n, m;
vector<vector<pair<ll, ll>>> g(M), gt(M), gscc(M), gtscc(M);
vector<Edge> edges;
vector<ll> scc(M), post;
ll nxt = 1;
void post_dfs(ll v) {
if(scc[v]) return;
scc[v] = 1;
for(auto[u, k] : g[v]) post_dfs(u);
post.push_back(v);
}
void trans_dfs(ll v) {
scc[v] = nxt;
for(auto[u, k] : gt[v]) if(!scc[u]) trans_dfs(u);
}
vector<vector<ll>> bfs(ll s, bool odw, int fa, int fb) {
vector<vector<ll>> dist(M, vector<ll>(2, LLONG_MAX));
dist[s][0] = 0;
queue<pair<ll, ll>> Q;
Q.push({s, 0});
while(Q.size()) {
auto[v, d] = Q.front(); Q.pop();
if(v==scc[n] && d==0) {
if(dist[v][1] > dist[v][0]) {
dist[v][1] = dist[v][0];
Q.push({v, 1});
}
}
for(auto[u, k] : (odw ? gtscc[v] : gscc[v])) {
if(v==fa && u==fb) continue;
if(dist[u][d] > dist[v][d] + 1) {
dist[u][d] = dist[v][d] + 1;
Q.push({u, d});
}
}
}
return dist;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(ll i=0; i<m; ++i) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
g[a].push_back({b, i});
gt[b].push_back({a, i});
Edge e = {a, b, c, d};
edges.emplace_back(e);
}
for(int i=1; i<=n; ++i) post_dfs(i);
scc.assign(M, 0);
reverse(post.begin(), post.end());
for(auto v : post) {
if(!scc[v]) {
trans_dfs(v);
nxt++;
}
}
if(scc[1] == scc[n]) {
cout << "0\n";
return 0;
}
//for(int i=1; i<=n; ++i) cout << scc[i] << " "; cout << "\n";
ll ans = LLONG_MAX;
vector<Edge> scc_edges;
for(ll i=1; i<=n; ++i) {
for(auto[u, k] : g[i]) {
if(scc[i]!=scc[u]) {
gscc[scc[i]].push_back({scc[u], k});
gtscc[scc[u]].push_back({scc[i], k});
edges[k].a = scc[edges[k].a];
edges[k].b = scc[edges[k].b];
scc_edges.push_back(edges[k]);
}
}
}
vector<vector<ll>> distG = bfs(scc[1], 0, -1, -1);
vector<vector<ll>> distGT = bfs(scc[1], 1, -1, -1);
bool moze1n = 0;
bool mozen1 = 0;
int ile1n = 0;
int ilen1 = 0;
for(auto e : scc_edges) {
auto[a, b, c, d] = e;
if(a==scc[1] && b==scc[n]) ile1n++;
if(a==scc[n] && b==scc[1]) ilen1++;
}
if(ile1n > 1) moze1n = 1;
if(ilen1 > 1) mozen1 = 1;
moze1n |= (bfs(scc[1], 0, scc[1], scc[n])[scc[n]][0] < LLONG_MAX);
mozen1 |= (bfs(scc[n], 0, scc[n], scc[1])[scc[1]][0] < LLONG_MAX);
for(auto e : scc_edges) {
auto[a, b, c, d] = e;
if(a==scc[1] && b==scc[n] && !moze1n) continue;
if(a==scc[n] && b==scc[1] && !mozen1) continue;
if(distG[b][0]<LLONG_MAX && distGT[a][1]<LLONG_MAX) {
ans = min(ans, d);
//cout << a << " " << b << "\n";
}
if(distG[b][1]<LLONG_MAX && distGT[a][0]<LLONG_MAX) {
ans = min(ans, d);
//cout << a << " " << b << "\n";
}
}
if(ans==LLONG_MAX) cout << "-1\n";
else cout << ans << "\n";
return 0;
}
