#include<bits/stdc++.h>
using namespace std;
const int MX = 205;
const int INF = 2e9+10;
const int MXM = 5e4 + 5;
struct Edge {
int from, to, len, invert, id;
bool vip;
Edge() {vip = 0;}
Edge(int _to, int _len, int _invert, int _id) {
to = _to, len = _len, invert = _invert, id = _id;
vip = 0;
}
Edge(int _from, int _to, int _len, int _invert, int _id) {
from = _from, to = _to, len = _len, invert = _invert, id = _id;
vip = 0;
}
} List[MXM];
int n, m;
vector<vector<Edge>>g(MX, vector<Edge>()), gt(MX, vector<Edge>());
int to_one[MX], to_n[MX], from_one[MX], from_n[MX];
int dad[MX];
void dijkstra(int sc, vector<vector<Edge>>&gr, int *a) {
a[sc] = 0;
priority_queue<pair<int,int>>pq;
pq.emplace(0, sc);
while(!pq.empty()) {
int v, cost;
tie(cost, v) = pq.top();
pq.pop();
cost = -cost;
if(a[v]!=cost) continue;
for(auto e : gr[v]) {
if(cost+e.len<a[e.to]) {
a[e.to] = cost+e.len;
pq.emplace(-a[e.to], e.to);
dad[e.to] = e.id;
}
}
}
}
void dijkstra2(int sc, int ban, int* a) {
a[sc] = 0;
priority_queue<pair<int,int>>pq;
pq.emplace(0, sc);
while(!pq.empty()) {
int v, cost;
tie(cost, v) = pq.top();
pq.pop();
cost = -cost;
if(a[v]!=cost) continue;
for(auto e : g[v]) if(e.id!=ban) {
if(cost+e.len<a[e.to]) {
a[e.to] = cost+e.len;
pq.emplace(-a[e.to], e.to);
}
}
}
}
void PlayGround() {
cin>>n>>m;
for(int i=0; i<m; ++i) {
int u, v, c, d;
cin>>u>>v>>c>>d;
g[u].emplace_back(Edge(v, c, d, i));
gt[v].emplace_back(Edge(u, c, d, i));
List[i] = {u, v, c, d, i};
}
for(int i=1; i<=n; ++i) {
to_one[i] = to_n[i] = from_one[i] = from_n[i] = INF;
}
dijkstra(1, g, from_one);
int cur = n;
while(cur!=1 && from_one[n]!=INF) {
List[dad[cur]].vip = 1;
cur = List[dad[cur]].from;
}
dijkstra(n, g, from_n);
cur = 1;
while(cur!=n && from_n[1]!=INF) {
List[dad[cur]].vip = 1;
cur = List[dad[cur]].from;
}
dijkstra(1, gt, to_one);
dijkstra(n, gt, to_n);
for(int i=1; i<=n; ++i) {
for(auto &e : g[i]) {
e = List[e.id];
}
}
int ans = INF;
if(from_one[n]!=INF && from_n[1]!=INF) {
ans = from_one[n] + from_n[1];
}
for(int u=1; u<=n; ++u) {
for(auto e : g[u]) if(e.vip==false) {
int v, c, d;
v = e.to, c = e.len, d = e.invert;
//1->v->u->n->1
if(from_one[v]!=INF && to_n[u]!=INF && from_n[1]!=INF) {
ans = min(ans, from_one[v]+to_n[u]+from_n[1]+c+d);
}
//1->n->v->u->1
if(from_one[n]!=INF && from_n[v]!=INF && to_one[u]!=INF) {
ans = min(ans, from_one[n]+from_n[v]+to_one[u]+c+d);
}
}
}
for(int i=1; i<=n; ++i) {
from_one[i] = from_n[i] = INF;
}
for(int i=1; i<=n; ++i) {
for(auto e : g[i]) if(e.vip) {
dijkstra2(1, e.id, from_one);
dijkstra2(n, e.id, from_n);
int u, v, c, d;
u = e.from, v = e.to, c = e.len, d = e.invert;
//1->v->u->n->1
if(from_one[v]!=INF && to_n[u]!=INF && from_n[1]!=INF) {
ans = min(ans, from_one[v]+to_n[u]+from_n[1]+c+d);
}
//1->n->v->u->1
if(from_one[n]!=INF && from_n[v]!=INF && to_one[u]!=INF) {
ans = min(ans, from_one[n]+from_n[v]+to_one[u]+c+d);
}
}
}
if(ans==INF) ans = -1;
cout<<ans<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
