#include <bits/stdc++.h>
using namespace std;
#define int long long
int cost[100003] ;
int aa[100003],bb[100003],dd[100003] ;
set <int> adj[203] ;
set <int> adj2[203] ;
int used[100003] ;
int n,m ;
bool ok=0 ;
void con(int xx){
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] ;
used[id]=1 ;
if (id-m>=0) used[id-m]=1 ;
}
}
}
if (vis[n]) ok=1 ;
}
int dij(int xx){
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() ;
// cout << x << endl ;
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] ;
}
}
}
// cout << xx << endl ; cout << endl ;
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) ;
aa[i+m]=bb[i],bb[i+m]=aa[i],dd[i+m]=dd[i],cost[i+m]=cost[i] ;
adj2[aa[i]].insert(i) ;
adj2[bb[i]].insert(i+m) ;
}
con(1) ;
int tt=0 ;
tt+=dij(1) ;
tt+=dij(n) ;
int mn=tt ;
for (i = 0 ; i < m ; i ++){
if (!ok||used[i]){
// cout << i ;
int tt=0 ;
adj[aa[i]].erase(i) ;
swap(aa[i],bb[i]) ;
adj[aa[i]].insert(i) ;
tt+=dij(1) ;
tt+=dij(n) ;
// cout << i << " " << tt << endl ;
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]) ;
}
}
if (mn>=LLONG_MAX/4){
cout << -1 << endl ;
return 0 ;
}
cout << mn << endl ;
return 0;
}
