#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
vector<ll> parent;
vector<ll> dijkstra(ll s, vector<vector<pair<pair<ll,ll>,ll>>> adj) {
vector<ll> dist(n+1, 1e18);
parent.resize(n+1,-1);
dist[s] = 0;
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
pq.push({0, s});
while(!pq.empty()) {
auto [d,u] = pq.top();
pq.pop();
if (d>dist[u]) continue;
for (auto e : adj[u]) {
ll v = e.first.first;
ll w = e.first.second;
ll idx = e.second;
if (dist[v]>dist[u]+w) {
dist[v] = dist[u]+w;
parent[v] = idx;
pq.push({dist[v], v});
}
}
}
return dist;
}
vector<vector<pair<pair<ll,ll>,ll>>> adj2;
ll dijkstra1(ll s, ll f, ll idx) {
vector<ll> dist(n+1, 1e18);
dist[s] = 0;
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
pq.push({0, s});
while(!pq.empty()) {
auto [d,u] = pq.top();
pq.pop();
if (d>dist[u]) continue;
for (auto e : adj2[u]) {
ll v = e.first.first;
ll w = e.first.second;
ll idx1 = e.second;
if (idx1==idx) swap(v,w);
if (dist[v]>dist[u]+w) {
dist[v] = dist[u]+w;
pq.push({dist[v], v});
}
}
}
return dist[f];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
vector<ll> uu(m), vv(m), cc(m), dd(m);
vector<vector<pair<pair<ll,ll>,ll>>> adj(n+1);
vector<vector<pair<pair<ll,ll>,ll>>> adj1(n+1);
for (int i=0; i<m; i++) {
cin >> uu[i] >> vv[i] >> cc[i] >> dd[i];
adj[uu[i]].push_back({{vv[i], cc[i]}, i});
adj1[vv[i]].push_back({{uu[i], cc[i]}, i});
}
vector<ll> dist1 = dijkstra(1, adj);
vector<ll> check(m);
if (dist1[n]!=1e18) {
ll curr = n;
while (curr!=1) {
ll idx = parent[curr];
check[idx] = 1;
curr = uu[idx];
}
}
vector<ll> dist2 = dijkstra(n, adj);
if (dist2[1]!=1e18) {
ll curr = 1;
while (curr!=n) {
ll idx = parent[curr];
check[idx] = 1;
curr = uu[idx];
}
}
vector<ll> dist3 = dijkstra(1, adj1);
vector<ll> dist4 = dijkstra(n, adj1);
ll res = 1e18;
if (dist1[n]!=1e18 && dist2[1]!=1e18) res = dist1[n] + dist2[1];
adj2.resize(n);
for (int i=0; i<m; i++) {
ll d1, d2;
if (!check[i]) {
d1 = min(dist1[n], dist1[vv[i]]+cc[i]+dist4[uu[i]]);
d2 = min(dist2[1], dist2[vv[i]]+cc[i]+dist3[uu[i]]);
} else {
d1 = dijkstra1(1, n, i);
d2 = dijkstra1(n, 1, i);
}
if (d1!=1e18 && d2!=1e18) {
res = min(res, d1+d2+dd[i]);
}
}
if (res==1e18) cout << -1;
else cout << res;
}
