#include <bits/stdc++.h>
#define forn(i,n) for(int i=0;i<int(n);++i)
#define fort(i,n) for(int i=0;i<=int(n);++i)
#define fori(i,a,n) for(int i=a;i<int(n);++i)
#define forit(i,a,n) for(int i=a;i<=int(n);++i)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define LINE cerr<<"===================================="<<endl
using namespace std;
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
os<<"[";
forn(i,v.size()){
if(i) os<<" ";
os<<v[i];
}
os<<"]";
return os;
}
typedef long long ll;
typedef long double ld;
const int INF = 1e9;
struct Edge{
int u, v, w, d;
};
struct G{
struct E{
int v, w, i;
};
struct D{
vector<int> dist;
vector<int> back;
D(int n): dist(n, INF), back(n) {}
};
vector<vector<E>> g;
G(int n): g(n) {}
void add(int u, int v, int w, int i){
g[u].push_back({v,w,i});
}
void pop(int u){ // Eliminar arista agregada temporalmente
g[u].pop_back();
}
D dijkstra(int s, int p){ // source y prohibida (-1 si no hay)
D ret(SZ(g));
priority_queue<pair<int,int>> dij;
ret.dist[s] = 0;
dij.push({0, s});
while(SZ(dij)){
int d = -dij.top().first, u = dij.top().second;
dij.pop();
if(ret.dist[u] != d) continue;
for(auto [v, w, i]: g[u]){
if(i == p) continue;
int nd = d + w;
if(nd < ret.dist[v]){
ret.dist[v] = nd;
ret.back[v] = i;
dij.push({-nd, v});
}
}
}
return ret;
}
};
void solve(){
int n, m;
cin>>n>>m;
vector<Edge> es(m);
for(Edge &e: es) cin>>e.u>>e.v>>e.w>>e.d;
G g(n+1), h(n+1);
forn(i,m){
g.add(es[i].u, es[i].v, es[i].w, i);
h.add(es[i].v, es[i].u, es[i].w, i);
}
G::D fromS = g.dijkstra(1,-1);
G::D fromN = g.dijkstra(n,-1);
G::D toS = h.dijkstra(1,-1);
G::D toN = h.dijkstra(n,-1);
//~ DBG(fromS.dist);
//~ DBG(toN.dist);
//~ DBG(fromN.dist);
//~ DBG(toS.dist);
set<int> pathSN, pathNS;
{
int a = 1, b = n;
forn(_,2){
while(fromS.back[b]){
int i = fromS.back[b];
pathSN.insert(i);
b = es[i].u;
}
swap(a,b);
swap(fromS,fromN);
swap(pathSN,pathNS);
}
}
// TODO: Cambiar cositas a ll
ll costSN = fromS.dist[n];
ll costNS = fromN.dist[1];
//~ DBG2(costSN, costNS);
ll ans = min((ll) INF, costSN + costNS);
forn(i,m){
int u = es[i].u, v = es[i].v, w = es[i].w, d = es[i].d;
ll auxSN = costSN;
ll auxNS = costNS;
if(pathSN.count(i)){
auxSN = INF;
// TODO: Recalcular camino
g.add(v, u, w, -1);
G::D fromSTemp = g.dijkstra(1, i);
g.pop(v);
auxSN = fromSTemp.dist[n];
} else{
auxSN = min(auxSN, (ll)fromS.dist[v] + es[i].w + toN.dist[u]);
}
if(pathNS.count(i)){
auxNS = INF;
// TODO: Recalcular camino
g.add(v, u, w, -1);
G::D fromNTemp = g.dijkstra(n, i);
g.pop(v);
auxNS = fromNTemp.dist[1];
} else{
auxNS = min(auxNS, (ll)fromN.dist[v] + es[i].w + toS.dist[u]);
}
ll aux = auxSN + auxNS + d;
//~ if(aux == 1){
//~ DBG4(i, auxSN, auxNS, d);
//~ }
ans = min(ans, aux);
}
if(ans == INF) ans = -1;
cout<<ans<<"\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
assert(freopen("input.in", "r", stdin));
//~ freopen("output.out", "w", stdout);
#endif
#ifdef LOCAL
int tcs; cin>>tcs;
while(tcs--)
#endif
solve();
return 0;
}
