#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define mp make_pair
#define sz(x) (int)(x).size()
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
void ckmin(ll& a, ll b){
a = min(a, b);
}
const int mx = 50005;
const ll INF = 1e18;
int N, M;
int U[mx];
int V[mx];
int C[mx];
int D[mx];
vi adj[mx];
vi S = vi{0, 0};
vi spath[2]; //edge list of shortest path
int forbidden = -1; //forbidden edge
ll dist[mx];
ll o_dist[2][2][mx];
pi from[mx];
void genDist(int typ, int disallowed = -1){
forbidden = disallowed;
for(int i = 1; i <= N; i++){
dist[i] = INF;
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dist[S[typ]] = 0;
pq.push(mp(dist[S[typ]], S[typ]));
while(sz(pq)){
int node = pq.top().s;
pq.pop();
for(auto u: adj[node]){
if(u == forbidden) continue;
int neigh = V[u];
ll cost = C[u];
if(dist[neigh] > dist[node]+cost){
dist[neigh] = dist[node]+cost;
from[neigh] = mp(node, u);
pq.push(mp(dist[neigh], neigh));
}
}
}
}
void reverseEdges(){
for(int i = 1; i <= N; i++){
adj[i].clear();
}
for(int i = 1; i <= M; i++){
swap(U[i], V[i]);
}
for(int i = 1; i <= M; i++){
adj[U[i]].pb(i);
}
}
bool spec[mx];
int main(){
cin >> N >> M;
for(int i = 1; i <= M; i++){
cin >> U[i] >> V[i] >> C[i] >> D[i];
adj[U[i]].pb(i);
}
S[0] = 1;
S[1] = N;
ll ans = 0;
for(int typ = 0; typ < 2; typ++){
genDist(typ);
ans+=dist[S[1-typ]]; //initialize to initial shortest paths
// for(int i = 1; i <= N; i++){
// cout << i << " " << dist[i] << "\n";
// }
// cout << dist[S[1-typ]] << "\n";
if(dist[S[1-typ]] != INF){
int curnode = S[1-typ];
while(curnode != S[typ]){
spath[typ].pb(from[curnode].s);
curnode = from[curnode].f;
}
reverse(all(spath[typ]));
}
for(int i = 1; i <= N; i++){
o_dist[typ][0][i] = dist[i];
}
}
reverseEdges();
for(int typ = 0; typ < 2; typ++){
genDist(typ);
for(int i = 1; i <= N; i++){
o_dist[typ][1][i] = dist[i];
}
}
reverseEdges();
for(int typ = 0; typ < 2; typ++){
for(auto ed: spath[typ]){
spec[ed] = 1;
ll pans = D[ed];
U[M+1] = V[ed];
V[M+1] = U[ed];
C[M+1] = C[ed];
adj[V[ed]].pb(M+1);
genDist(0, ed);
pans+=dist[S[1]];
genDist(1, ed);
adj[V[ed]].pop_back();
pans+=dist[S[0]];
ckmin(ans, pans);
}
}
// for(int ed = 1; ed <= M; ed++){
// spec[ed] = 1;
// ll pans = D[ed];
// U[M+1] = V[ed];
// V[M+1] = U[ed];
// C[M+1] = C[ed];
// adj[V[ed]].pb(M+1);
// genDist(0, ed);
// pans+=dist[S[1]];
// genDist(1, ed);
// adj[V[ed]].pop_back();
// pans+=dist[S[0]];
// ckmin(ans, pans);
// }
for(int i = 1; i <= M; i++){
if(spec[i]) continue;
ll pans = D[i];
pans+=min(o_dist[0][0][S[1]], o_dist[0][0][V[i]]+o_dist[1][1][U[i]]+C[i]);
pans+=min(o_dist[1][0][S[0]], o_dist[1][0][V[i]]+o_dist[0][1][U[i]]+C[i]);
// cout << i << " " << pans << "\n";
// cout << o_dist[0][0][S[1]] << " " << o_dist[1][0][S[0]] << "\n";
ckmin(ans, pans);
}
if(ans >= INF){
cout << -1 << "\n";
}
else{
cout << ans << "\n";
}
}
