#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=310;
const int inf=1e18;
const int mod=1e9+7;
vector<array<int,3>>g[N];
int dist[N][N], dd[N];
int djikstra(int vu,int uv) {
for(int i=1;i<N;i++) dd[i]=inf;
set<pair<int,int>>st;
dd[vu]=0;
st.insert({0,vu});
while(!st.empty()) {
int v=st.begin() -> second;
st.erase(st.begin());
for(auto [to,w,ww]:g[v]) {
if(dd[to]>dd[v]+w) {
st.erase({dd[to],to});
dd[to]=dd[v]+w;
st.insert({dd[to],to});
}
}
}
return dd[uv];
}
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
int T=1;
// cin>>T;
while(T--) {
int n,m;
cin>>n>>m;
vector<array<int,4>>e;
for(int i=1;i<=m;i++) {
int v,u,c,d;
cin>>v>>u>>c>>d;
g[v].pb({u,c,d});
e.pb({v,u,c,d});
}
for(int vu=1;vu<=n;vu++) {
set<pair<int,int>>st;
for(int i=1;i<=n;i++) {
dist[vu][i]=inf;
}
st.insert({0,vu});
dist[vu][vu]=0;
while(!st.empty()) {
int v=st.begin() -> second;
st.erase(st.begin());
for(auto [to,w,d]:g[v]) {
if(dist[vu][to]>dist[vu][v]+w) {
st.erase({dist[vu][to],to});
dist[vu][to]=dist[vu][v]+w;
st.insert({dist[vu][to],to});
}
}
}
}
int ans=dist[1][n]+dist[n][1];
for(auto [v,u,c,d]:e) {
if(ans>min(dist[1][n],dist[1][u]+dist[v][n])+min(dist[n][1],dist[n][u]+dist[v][1])+c+d) {
array<int, 3> it={u,c,d};
g[v].erase(find(g[v].begin(),g[v].end(),it));
g[u].pb({v,c,d});
ans=min(ans,djikstra(1,n)+djikstra(n,1)+d);
g[u].pop_back();
g[v].pb({u,c,d});
}
}
cout<<(ans < inf ? ans : -1);
}
}
