#include <bits/stdc++.h>
using namespace std;
#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif
using ll = long long;
const ll inf = 1'000'000'000'000'000'000;
#define int long long
int n;
vector<vector<pair<int, int>>> v;
vector<int> dij(int start, vector<vector<pair<int, int>>> &g){
vector<int> d(n, inf);
d[start] = 0;
set<pair<int, int>> q;
for(int i = 0; i < n; i++){
q.insert({d[i], i});
}
while(!q.empty()){
auto [dd, u] = *q.begin();
q.erase(q.begin());
for(auto [i, j] : g[u]){
if(dd + j < d[i]){
q.erase({d[i], i});
d[i] = dd + j;
q.insert({d[i], i});
}
}
}
return d;
}
void solve(){
int m;
cin >> n >> m;
v.resize(n);
vector<array<int, 4>> z(m);
for(int i = 0; i < m; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
a--;b--;
z[i] = {a, b, c, d};
}
v.clear();
v.resize(n);
for(int i = 0; i < m; i++){
auto [a, b, c, d] = z[i];
v[a].emplace_back(b, c);
}
int ans = inf;
auto d1 = dij(0, v);
auto d2 = dij(n - 1, v);
ans = min(ans, d1[n - 1] + d2[0]);
for(int ind = 0; ind < m; ind++){
v.clear();
v.resize(n);
for(int i = 0; i < m; i++){
auto [a, b, c, d] = z[i];
if(i != ind){
v[a].emplace_back(b, c);
}else{
v[b].emplace_back(a, c);
}
}
auto d1 = dij(0, v);
auto d2 = dij(n - 1, v);
ans = min(ans, d1[n - 1] + d2[0] + z[ind][3]);
}
cout << ans << endl;
}
signed main(){
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
