#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e4+5;
int n,m,d[N][2],d1[N][2],d2[N][2],check[N],check1[N],mark[N];
pii trace[N][2];
struct edges{
int id,v,w,p;
};
vector<edges>adj[N],adj1[N];
void dijkstra(int u, int type){
for(int i = 1; i <= n; i++) d[i][type] = 1e18;
d[u][type] = 0;
priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.push({0,u});
while(!pq.empty()){
auto[c,uu] = pq.top();
pq.pop();
if(c > d[uu][type]) continue;
for(auto[id,v,w,p]: adj[uu]){
if(d[v][type] > c+w){
d[v][type] = c+w;
trace[v][type] = {uu,id};
pq.push({d[v][type],v});
}
}
}
}
void dijkstra1(int u, int type){
for(int i = 1; i <= n; i++) d1[i][type] = 1e18;
d1[u][type] = 0;
priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.push({0,u});
while(!pq.empty()){
auto[c,uu] = pq.top();
pq.pop();
if(c > d1[uu][type]) continue;
for(auto[id,v,w,p]: adj1[uu]){
if(d1[v][type] > c+w){
d1[v][type] = c+w;
pq.push({d1[v][type],v});
}
}
}
}
void redijkstra(int u, int type){
for(int i = 1; i <= n; i++) d2[i][type] = 1e18;
d2[u][type] = 0;
priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.push({0,u});
while(!pq.empty()){
auto[c,uu] = pq.top();
pq.pop();
if(c > d2[uu][type]) continue;
for(auto[id,v,w,p]: adj[uu]){
if(mark[id]) continue;
if(d2[v][type] > c+w){
d2[v][type] = c+w;
pq.push({d2[v][type],v});
}
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u,v,w,p;
cin >> u >> v >> w >> p;
adj[u].push_back({i,v,w,p});
adj1[v].push_back({i,u,w,p});
}
dijkstra(1,0);
int x = n;
while(x != 1 && trace[x][0].fi != 0){
pii cc = trace[x][0];
check[cc.se] = 1;
x = cc.fi;
}
dijkstra(n,1);
x = 1;
while(x != n && trace[x][1].fi != 0){
pii cc = trace[x][1];
check1[cc.se] = 1;
x = cc.fi;
}
dijkstra1(1,0);
dijkstra1(n,1);
int ans = d[n][0]+d[1][1];
int ans1 = d[n][0];
int ans2 = d1[1][1];
for(int i = 1; i <= n; i++){
for(auto[id,v,w,p]: adj[i]){
if(!check[id] && !check1[id]){
ans = min({ans,d[1][1]+d[v][0]+d1[i][1]+w+p,d[n][0]+d[v][1]+d1[i][0]+w+p,d[v][0]+d1[i][1]+d[v][1]+d1[i][0]+2*w+p});
// int x = min(d[n][0],d[v][0]+d1[i][1]+w+p);
// int y = min(d1[1][1],d1[v][0]+d[i][1]+w+p);
// cout << id << " " << d1[v][1] << " " << d[i][0] << " " << v << " " << i << "\n";
// ans = min(ans,x+y);
//// ans1 = min(ans1,d[v][0]+d1[i][1]+d[v][1]+d1[i][0]+2*w;
//// ans2 = min(ans2,d[v][1]+d1[i][0]+w+p);
}
else{
mark[id] = 1;
adj[v].push_back({50001,i,w,p});
redijkstra(1,0);
redijkstra(n,1);
ans = min(ans,d2[n][0]+d2[1][1]+p);
mark[id] = 0;
adj[v].pop_back();
}
}
}
//cout << ans1 << "\n";
// int ans2 = d1[1][1];
// for(int i = 1; i <= n; i++){
// for(auto[id,v,w,p]: adj[i]){
// if(!check1[id]) ans2 = min(ans2,d[v][1]+d1[i][0]+w+p);
// else{
// mark[id] = 1;
// adj[v].push_back({-1,v,w,p});
// redijkstra(n,1);
// ans2 = min(ans2,d2[1][1]+p);
// mark[id] = -1;
// adj[v].pop_back();
// }
// }
// }
if(ans > 1e17) cout << -1;
else cout << ans;
}
//
// +.::=. .*: -.
// -- :. = -:--
// .= .. .-=++*+++=:. = :
// .= ....:=%@@@@@*: . :.
// .-+=..: :. .+##%##+. .: .+:
// :*@**%* .. :. ::..:.:. --:
// .--. +@@@@@%: .==: .###@*
// :-- -: -:@@@@# - =@@@@#. .= : +
// .: -=--==: == +- :*%*++= .:#
// -. .:. . +. -*. =@@. .-. .=
// +=.. .. -- .* .#. +@# - :==*=
// .=.+=:::: =. =- ##@+ :--+.#@%++%*
// .++@@: = + .%%%%@@@@@@@@@@@@@@%. :-@#-: -@.
// :@@@@= .+ .= *# .#@.=- =@::-:@:
// :-@@%. -- -- :@*. .%# +. - ** :=%. .*@#
// :-. .-*-. -: +. %-=::@# .* : - :%- +%.+@+@@
// .- :. **: +: = # : =* =@# -= # #@@@:-@ :*@@. %@
// -=: :: .* .= + # =..@ .*. +. *. *#=.+%@*-%* %@
// :=. :.. .: +. -= .+ # -- #. =- .+ +: =@+ .+-++ @%
// ++-=. * -- := # :- +- :* =:+: -@# :@#*%@@@%@+
// *. -- -- := # .= #@#=. +- :=+: :%@-#@@@#@+:@@#
// + +. -- := # .= := .+. +*. *@@+=@-=@*-.#@.
// = + := .+ # = .= .#.-@. -+ .%# -@@= @#
// .= .= .+ + *. = .+.. :*@ == =@. -#@#: @%
// .= .= * + =: .=.**: =--: # * *- %* =*=@+#@:
// .= := # =. .+ . .= --.#@@@@@#@@@: * -= #..@= **:@@@:
// + .= +: -- + # := +@%:@#: -:%= === #..* .#@@%@+.@@+
// * .= .* .= -:-= :- #= ++ =- =@. *: .* -*: : . .@@%
// * + * +. :- # -- # *: .@@ %- + =- +-.- :. .@@@.
// -: =: := .* +.-- =:-- .*.:.: # .= + *+ - :@%@=
// + * *:+. == .+ +. +.# .=-:=- -- -- =+: = -@#%*
// + -= *== *. -=-- :+-= ::: =: + %:. = %@+##
// .= +: +*- + +:+. +:*. .+ +: #.:. - .+ -@@=#%
// -. =. :=#- := =:* .-==#+- +: =- +:-..- :%* =@@:*%
// .- +. --+= .**%+-:. -* +-:*:.:. =@@* :-@@ *%
// -. += -+== -*#- =- .. .%@#@=.--@* *%
// =. .+: :+-*-=+: +%+*@@%%@-= +@- *#
// -::= :**=: :@@@@@@%@@- #@ #*
// -: +: - .@@#%@@%@@: :@# .#+
// :- :#= -- :@@@#@-=@#. =@- .%=
// =:.@@%= =# .+.=. +@@@@* -*: #% :@:
// .+ *@@@@@@@@* :@@*@@@* .@+ -@.
// .+=%@*%@@@@@#: =@@@%:.: +@: +%
// .=%@%#@@@@##@*: =%@@@#: @# ##
// :#@%@@@@#@@@@+ :*. @: =@- .@+
// .+@%#%@@:=-.. .=: %*==+. @% -@-
// =. =: :-:.:: .-- .= -: =@- -
// .- :-. :: .- =-:
// .=+-.=-.*- = -..+*: .-:.- = .+*# ....
// =. -= -: .. -. +. -. +. -+ -*=: +.
// .- +- * -.* #+ .+ =. :=
// :- --=*: -+ *= -# - -##+-.. .:+#: +.
// :- = --=:==+*. =: .: .= =**= = .+
// .= + =-- :- .=. -- .- =
// = .- --: .-+*@%*# +. + :-
// + +- -:- :*@@@@@@*@#*@@%*=: =: - -.
// .* - ::+ =@@@@#-.-@@%%@@+=%@@@%= -:: = :-
// .+ :. +-. #@@@= +@@@-#@@%. +@@@+ .:= .- +:
// .--. -. :=- :@@+ :@@@@# =@@@# -%@# -= :: :-+-
// * - + --. +@@#=%@@@@@. :@@@@% :%@ := =. -=+
// .-**- -. -- .%@@@@+%@+ @@+%@@*-+@@@. :=. - :+*-
// :===-==. .-= *@% *@= +%%##=. :=: :. .::-==-.
// .::-=+=+=-:. #%: -#: .-*#+===-:.
// ..::---====---::.
