#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N = 310;
const int M = 5e4+10;
const ll INF = 1e16;
int n,m;
vector <int> G[N];
vector <int> vec[2];
ll dis[N][N][2];
ll path0, path1;
int par[N];
bool hame[M][2];
ll ans;
void Input();
void Dijkstra(int,int,int);
void Halat0_0();
void Halat1_0();
void Halat0_1();
void Path_0();
void Path_1();
struct edge{
ll u, v, w, c;
};
edge e[N];
int main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
Input();
Dijkstra(0, -1, 0);
if(dis[0][n-1][0] != INF)
Path_0();
Dijkstra(n-1, -1, 0);
if(dis[n-1][0][0] != INF)
Path_1();
for(int i = 1;i < n-1;i++)
Dijkstra(i, -1, 0);
path0 = dis[0][n-1][0], path1 = dis[n-1][0][0];
ans = path0 + path1;
Halat0_0();
Halat0_1();
Halat1_0();
if(ans >= INF)
cout << -1 << endl;
else
cout << ans << endl;
}
void Input(){
cin >> n >> m;
for(int i = 0;i < m;i++){
int u, v, w, c;
cin >> u >> v >> w >> c, u--, v--;
e[i].u = u, e[i].v = v, e[i].w = w, e[i].c = c;
G[u].push_back(i), G[v].push_back(i);
}
}
void Dijkstra(int s,int swp,int type){
set<pii> st;
bool mark[N];
fill(mark, mark + n, 0);
for(int i = 0;i < n;i++)
dis[s][i][type] = INF;
dis[s][s][type] = 0, par[s] = -1;
st.insert({0, s});
while(st.size()){
int a = st.begin() -> second;
if(!mark[a]){
mark[a] = true;
for(auto i : G[a]){
int w = e[i].w, u = e[i].u, v = e[i].v;
if(a == u and i != swp){
if(dis[s][v][type] > dis[s][u][type] + w)
dis[s][v][type] = dis[s][u][type] + w, par[v] = i, st.insert({dis[s][v][type], v});
}else if(a == v and i == swp){
if(dis[s][u][type] > dis[s][v][type] + w)
dis[s][u][type] = dis[s][v][type] + w, par[u] = i, st.insert({dis[s][u][type], u});
}
}
}
st.erase(st.begin());
}
}
void Path_0(){
int v = n-1;
while(par[v] != -1){
vec[0].push_back(par[v]);
hame[par[v]][0] = true;
v = e[par[v]].u;
}
}
void Path_1(){
int v = 0;
while(par[v] != -1){
vec[1].push_back(par[v]);
hame[par[v]][1] = true;
v = e[par[v]].u;
}
}
void Halat0_0(){
for(int i = 0;i < m;i++){
ll u = e[i].u, v = e[i].v, w = e[i].w, cost = e[i].c;
if(dis[0][v][0] + w + dis[u][n-1][0] < path0)
if(dis[n-1][v][0] + w + dis[u][0][0] < path1)
ans = min(ans, path0 + path1 + w + cost);
}
}
void Halat0_1(){
for(int i = 0;i < m;i++){
ll u = e[i].u, v = e[i].v, w = e[i].w, cost = e[i].c;
if(dis[0][v][0] + w + dis[u][n-1][0] < path0){
if(!hame[i][1])
ans = min(ans, dis[0][v][0] + w + dis[u][n-1][0] + path1 + cost);
else{
Dijkstra(n-1, i, 1);
ans = min(ans, dis[0][v][0] + w + dis[u][n-1][0] + dis[n-1][0][1] + cost);
}
}
}
}
void Halat1_0(){
for(int i = 0;i < m;i++){
ll u = e[i].u, v = e[i].v, w = e[i].w, cost = e[i].c;
if(dis[n-1][v][0] + w + dis[u][0][0] < path1){
if(!hame[i][0])
ans = min(ans, dis[n-1][v][0] + w + dis[u][0][0] + path0 + cost);
else{
Dijkstra(0, i, 1);
ans = min(ans, dis[n-1][v][0] + w + dis[u][0][0] + dis[0][n-1][1] + cost);
}
}
}
}
