#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 200, M = 5e4 ;
ll n, m, from[M + 1], to[M + 1], c[M + 1], d[M + 1] ;
set<pair<ll, ll>> v[N + 1] ;
ll deikstra(ll city, ll abu)
{
ll dist[N + 1] ;
set<pair<ll, ll>> s ;
for(ll i = 1 ; i <= N ; i++)
dist[i] = 1e15 ;
dist[city] = 0 ;
s.insert({0, city}) ;
while(s.size())
{
pair<ll, ll> p = *s.begin() ;
s.erase(p) ;
// cout << p.fi << ' ' << p.se << '\n' ;
if(p.fi > dist[p.se])
continue ;
for(auto i : v[p.se])
{
if(dist[i.fi] > p.fi + i.se)
{
// cout<<p.se<<"->"<<i.fi<<'\n';
dist[i.fi] = p.fi + i.se ;
s.insert({dist[i.fi], i.fi}) ;
}
}
}
return dist[abu] ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n >> m ;
for(ll i = 1 ; i <= m ; i++)
cin >> from[i] >> to[i] >> c[i] >> d[i] ;
if(m <= 1000)
{
ll ans ;
for(ll i = 1 ; i <= m ; i++)
v[from[i]].insert({to[i], c[i]}) ;
ans = deikstra(1, n) + deikstra(n, 1) ;
for(ll i = 1 ; i <= m ; i++)
{
ll now = d[i] ;
v[from[i]].erase({to[i], c[i]}) ;
v[to[i]].insert({from[i], c[i]}) ;
now += deikstra(1, n) ;
now += deikstra(n, 1) ;
ans = min(ans, now) ;
// cout << "___________________\n" ;
v[to[i]].erase({from[i], c[i]}) ;
v[from[i]].insert({to[i], c[i]}) ;
}
if(ans >= 1e15)
ans = -1 ;
cout << ans ;
return 0 ;
}
return 0 ;
}
