//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
#define int long long
const int inf = 1e18 + 7;
void solve(){
int n,m;
cin >> n >> m;
vector < vector < pair < int , int > > > graph(n+1) , igraph(n+1);
array < int , 4 > edge[m];
bool is_in_path[m];
memset(is_in_path , 0 , sizeof(is_in_path));
for(int i = 0;i<m;i++){
cin >> edge[i][0] >> edge[i][1] >> edge[i][2] >> edge[i][3];
graph[edge[i][0]].push_back({edge[i][1] , i});
igraph[edge[i][1]].push_back({edge[i][0] , i});
}
auto eval = [&](int st , vector < vector < pair < int , int > > > G , int forbidden){
vector < int > vis(n+1 , inf);
priority_queue < array < int , 3 > > pq;
pq.push({0 , st , -1});//3. buraya geldigim edge numarasi
while(pq.size()){
array < int , 3 > tmp = pq.top();//dist , node , past edge
pq.pop();
if(vis[tmp[1]] != inf)continue;
vis[tmp[1]] = -tmp[0];
if(forbidden == -1 and tmp[2] != -1)is_in_path[tmp[2]] = 1;
for(int i = 0;i<sz(G[tmp[1]]);i++){
pair < int , int > itr = G[tmp[1]][i];
if(itr.second == forbidden)continue;
pq.push({tmp[0] - edge[itr.second][2], itr.first , itr.second});
}
}
return vis;
};
vector < int > from1 = eval(1 , graph , -1);;
vector < int > fromn = eval(n , graph , -1);
vector < int > to1 = eval(1 , igraph , -1);
vector < int > ton = eval(n , igraph , -1);
int ans = from1[n] + fromn[1];
for(int i = 0;i<m;i++){
int r1 , r2;
if(is_in_path[i]){
// cout << "special : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl;
vector < int > tfrom1 = eval(1 , graph , i);
vector < int > tfromn = eval(n , graph , i);
vector < int > tto1 = eval(1 , igraph , i);
vector < int > tton = eval(n , igraph , i);
// cout << "tfrom1 : ";for(int i = 1;i<=n;i++)cout << tfrom1[i] << " ";cout << endl;
// cout << "tfromn : ";for(int i = 1;i<=n;i++)cout << tfromn[i] << " ";cout << endl;
// cout << "tto1 : ";for(int i = 1;i<=n;i++)cout << tto1[i] << " ";cout << endl;
// cout << "tton : ";for(int i = 1;i<=n;i++)cout << tton[i] << " ";cout << endl;
r1 = min(tfrom1[n] , tfrom1[edge[i][1]] + edge[i][2] + tton[edge[i][0]]);//gidis
r2 = min(tfromn[1] , tfromn[edge[i][1]] + edge[i][2] + tto1[edge[i][0]]);//donus
// cout << "r : " << r1 << " " << r2 << endl;
}
else{
// cout << "ordinary : " << edge[i][0] << " " << edge[i][1] << " " << edge[i][2] << " " << edge[i][3] << endl;
r1 = min(from1[n] , from1[edge[i][1]] + edge[i][2] + ton[edge[i][0]]);//gidis
r2 = min(fromn[1] , fromn[edge[i][1]] + edge[i][2] + to1[edge[i][0]]);//donus
// cout << "r : " << r1 << " " << r2 << endl;
}
ans = min(ans , edge[i][3] + r1 + r2);
}
cout << (ans >= inf ? -1 : ans) << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
