#include <bits/stdc++.h>
using namespace std;
#define int long long
int cost[50003] ;
int aa[50003],bb[50003],dd[50003] ;
set <int> adj[203] ;
int used[50003] ;
int n,m ;
int dij(int xx,int aaa){
priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q ;
vector <int> vis(203,0) ;
vector <int> dist(203,LLONG_MAX/4) ;
q.push({0,xx}) ;
dist[xx]=0 ;
while (!q.empty()){
auto [d,x]=q.top() ;
q.pop() ;
if (vis[x]) continue ;
vis[x]=1 ;
for (auto id : adj[x]){
if (dist[bb[id]]>d+dd[id]){
q.push({d+dd[id],bb[id]}) ;
dist[bb[id]]=d+dd[id] ;
if (aaa==1) used[id]=1 ;
}
}
}
if (xx==1) return dist[n] ;
else return dist[1] ;
}
signed main() {
int i,j ;
cin >> n >> m ;
for (i = 0 ; i < m ; i ++){
cin >> aa[i] >> bb[i] >> dd[i] >> cost[i] ;
adj[aa[i]].insert(i) ;
}
int tt=0 ;
tt+=dij(1,1) ;
tt+=dij(n,1) ;
if (tt>=LLONG_MAX/4){
cout << -1 << endl ;
return 0 ;
}
int mn=tt ;
for (i = 0 ; i < m ; i ++){
if (used[i]){
int tt=0 ;
adj[aa[i]].erase(i) ;
swap(aa[i],bb[i]) ;
adj[aa[i]].insert(i) ;
tt+=dij(1,0) ;
tt+=dij(n,0) ;
adj[aa[i]].erase(i) ;
swap(aa[i],bb[i]) ;
adj[aa[i]].insert(i) ;
mn=min(mn,tt+cost[i]) ;
}
else {
mn=min(mn,tt+cost[i]) ;
}
}
cout << mn << endl ;
return 0;
}
