#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAX=207;
const int MAX2=1e5+7;
pair<pair<int, int>, pair<ll, ll>> krawedzie[MAX2];
bool odw[MAX];
int n, m;
ll dijkstra(int v, int u){
vector<pair<int, ll>> G[MAX];
for (int i=0; i<m; i++){
G[krawedzie[i].first.first].push_back({krawedzie[i].first.second, krawedzie[i].second.first});
}
priority_queue<pair<ll, int>> Q;
Q.push({0, v});
for (int i=0; i<=n; i++) odw[i]=false;
while (!Q.empty()){
auto w=Q.top();
Q.pop();
if (odw[w.second]) continue;
odw[w.second] = true;
if (w.second==u) return -w.first;
for (auto k:G[w.second]){
if (odw[k.first]) continue;
Q.push({w.first-k.second, k.first});
}
}
return -1e18;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int a, b, c, d;
cin >> n >> m;
for (int i=0; i<m; i++){
cin >> a >> b >> c >> d;
krawedzie[i] = {{a, b}, {c, d}};
}
ll wyn=dijkstra(1, n)+dijkstra(n,1);
for (int i=0; i<m; i++){
a = krawedzie[i].first.first;
b = krawedzie[i].first.second;
krawedzie[i].first.first = b;
krawedzie[i].first.second = a;
if (wyn<0) wyn = dijkstra(1, n)+dijkstra(n, 1)+krawedzie[i].second.second;
else if (dijkstra(1, n)+dijkstra(n, 1)+krawedzie[i].second.second>0){
wyn = min(wyn, dijkstra(1, n)+dijkstra(n, 1)+krawedzie[i].second.second);
}
krawedzie[i].first.first = a;
krawedzie[i].first.second = b;
//cout << i << " " << wyn << endl;
}
if (wyn<0) cout << "-1\n";
else cout << wyn << "\n";
return 0;
}
