#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define pll pair<ll,ll>
const ll N=2e2,M=5e4;
ll n,m;
ll dist[N];
vector<ll>g[N];
struct Edge{
ll a,b,c,d;
Edge():a(-1),b(-1),c(-1),d(-1){}
};
Edge edge[M];
ll dijkstra(ll s,ll t){
fill(dist,dist+N,(ll)1e18);
dist[s]=0;
priority_queue<pll,vector<pll>,greater<pll>>pq;
pq.push({0,s});
while(!pq.empty()){
auto [D,x]=pq.top();
pq.pop();
if(dist[x]!=D) continue;
if(x==t) return dist[x];
for(ll i:g[x]){
if(edge[i].a==x){
if(dist[x]+edge[i].c<dist[edge[i].b]){
dist[edge[i].b]=dist[x]+edge[i].c;
pq.push({dist[edge[i].b],edge[i].b});
}
}
}
}
return (ll)1e18;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(ll i=0;i<m;i++){
cin>>edge[i].a>>edge[i].b>>edge[i].c>>edge[i].d;
edge[i].a--;
edge[i].b--;
g[edge[i].a].pb(i);
g[edge[i].b].pb(i);
}
ll ans=(ll)1e18;
for(ll i=0;i<=m;i++){
if(i<m){
swap(edge[i].a,edge[i].b);
ans=min(ans,dijkstra(0,n-1)+dijkstra(n-1,0)+edge[i].d);
swap(edge[i].a,edge[i].b);
}
else{
ans=min(ans,dijkstra(0,n-1)+dijkstra(n-1,0));
}
}
if(ans==(ll)1e18) ans=-1;
cout<<ans;
}
