#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int dist1[232][232];
int distn[232][232];
int rev1[232][232];
int revn[232][232];
int refer;
bool cmp5(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) {
return revn[refer][x.first.first] + x.first.second < revn[refer][y.first.first] + y.first.second;
}
bool cmp6(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) {
return rev1[refer][x.first.first] + x.first.second < rev1[refer][y.first.first] + y.first.second;
}
mt19937_64 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
return uniform_int_distribution<int>(x, y)(rng);
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
pair<pair<int,int>,pair<int,int> > e[m+1];
for(int i=1; i<=m; i++) { // O(m)
cin >> e[i].first.first >> e[i].first.second >> e[i].second.first >> e[i].second.second;
}
for(int i=0; i<=n; i++) { // O(n^2)
for(int j=0; j<=n; j++) {
dist1[i][j] = distn[i][j] = rev1[i][j] = revn[i][j] = 1e18;
}
dist1[i][1] = 0;
distn[i][n] = 0;
rev1[i][1] = 0;
revn[i][n] = 0;
}
for(int b=0; b<=n; b++) { // O(nm)
vector<pair<int, int> > adj[n+1], rev[n+1];
bool in[n+1];
deque<int> q;
for(int i=1; i<=m; i++) {
if(e[i].first.first != b && e[i].first.second != b) {
adj[e[i].first.first].push_back({e[i].first.second, e[i].second.first});
rev[e[i].first.second].push_back({e[i].first.first, e[i].second.first});
}
}
int tg, now;
for(int i=1; i<=n; i++) in[i] = 0;
in[1] = 1;
q.push_back(1);
tg = rnd(3, 12), now = 0;
while(q.size()) {
int f = q.front();
q.pop_front();
in[f] = 0;
for(pair<int, int> x: adj[f]) {
if(dist1[b][x.first] > dist1[b][f] + x.second) {
dist1[b][x.first] = dist1[b][f] + x.second;
if(!in[x.first]) {
in[x.first] = 1;
now++;
if(now == tg) tg = rnd(3, 12), now = 0, q.push_front(x.first);
q.push_back(x.first);
}
}
}
}
in[n] = 1;
q.push_back(n);
tg = rnd(3, 12), now = 0;
while(q.size()) {
int f = q.front();
q.pop_front();
in[f] = 0;
for(pair<int, int> x: adj[f]) {
if(distn[b][x.first] > distn[b][f] + x.second) {
distn[b][x.first] = distn[b][f] + x.second;
if(!in[x.first]) {
in[x.first] = 1;
now++;
if(now == tg) tg = rnd(3, 12), now = 0, q.push_front(x.first);
q.push_back(x.first);
}
}
}
}
in[1] = 1;
q.push_back(1);
tg = rnd(3, 12), now = 0;
while(q.size()) {
int f = q.front();
q.pop_front();
in[f] = 0;
for(pair<int, int> x: rev[f]) {
if(rev1[b][x.first] > rev1[b][f] + x.second) {
rev1[b][x.first] = rev1[b][f] + x.second;
if(!in[x.first]) {
in[x.first] = 1;
now++;
if(now == tg) tg = rnd(3, 12), now = 0, q.push_front(x.first);
q.push_back(x.first);
}
}
}
}
in[n] = 1;
q.push_back(n);
tg = rnd(3, 12), now = 0;
while(q.size()) {
int f = q.front();
q.pop_front();
in[f] = 0;
for(pair<int, int> x: rev[f]) {
if(revn[b][x.first] > revn[b][f] + x.second) {
revn[b][x.first] = revn[b][f] + x.second;
if(!in[x.first]) {
in[x.first] = 1;
now++;
if(now == tg) tg = rnd(3, 12), now = 0, q.push_front(x.first);
q.push_back(x.first);
}
}
}
}
}
int ans = dist1[0][n] + distn[0][1];
vector<pair<int,int> > adj[n+1], rev[n+1];
vector<int> adj_id[n+1];
for(int i=1; i<=m; i++) { // O(m)
adj_id[e[i].first.first].push_back(i);
adj[e[i].first.first].push_back({e[i].first.second, e[i].second.first});
rev[e[i].first.second].push_back({e[i].first.first, e[i].second.first});
}
int cnt[n+1][n+1];
for(int i=0; i<=n; i++) { // O(n^2)
for(int j=0; j<=n; j++) {
cnt[i][j] = 0;
}
}
for(int i=1; i<=m; i++) { // O(m)
cnt[e[i].first.first][e[i].first.second]++;
}
int opt1[n+1], opt2[n+1], opt3[n+1], opt4[n+1];
for(int i=1; i<=n; i++) { // O(m)
opt1[i] = opt2[i] = opt3[i] = opt4[i] = 1e18;
for(pair<int, int> x: adj[i]) {
opt1[i] = min(opt1[i], x.second + revn[i][x.first]);
opt3[i] = min(opt3[i], x.second + rev1[i][x.first]);
}
for(pair<int, int> x: rev[i]) {
opt2[i] = min(opt2[i], dist1[i][x.first] + x.second);
opt4[i] = min(opt4[i], distn[i][x.first] + x.second);
}
}
vector<pair<pair<int,int>, int> > opt5[n+1], opt6[n+1];
for(int i=1; i<=n; i++) { // O(m log m)
for(int j=0; j<adj[i].size(); j++) {
opt5[i].push_back({adj[i][j], adj_id[i][j]});
}
refer = i;
sort(opt5[i].begin(), opt5[i].end(), cmp5);
for(int j=0; j<adj[i].size(); j++) {
opt6[i].push_back({adj[i][j], adj_id[i][j]});
}
sort(opt6[i].begin(), opt6[i].end(), cmp6);
}
for(int i=1; i<=m; i++) { // O(m)
int forward, backward;
forward = dist1[e[i].first.first][e[i].first.second] + e[i].second.first;
int mi = (e[i].first.first == n ? 0 : 1e18);
mi = min(mi, opt1[e[i].first.first]);
forward += mi;
forward = min(forward, dist1[e[i].first.first][n]);
int pt1 = (e[i].first.first == 1 ? 0 : 1e18);
int pt2 = (e[i].first.first == n ? 0 : 1e18);
pt1 = min(pt1, opt2[e[i].first.first]);
for(pair<pair<int,int>, int> x: opt5[e[i].first.first]) {
if(x.second == i) {
continue;
}
pt2 = min(pt2, revn[e[i].first.first][x.first.first] + x.first.second);
break;
}
forward = min(forward, pt1 + pt2);
backward = distn[e[i].first.first][e[i].first.second] + e[i].second.first;
mi = (e[i].first.first == 1 ? 0 : 1e18);
mi = min(mi, opt3[e[i].first.first]);
backward += mi;
backward = min(backward, distn[e[i].first.first][1]);
pt1 = (e[i].first.first == n ? 0 : 1e18);
pt2 = (e[i].first.first == 1 ? 0 : 1e18);
pt1 = min(pt1, opt4[e[i].first.first]);
for(pair<pair<int,int>, int> x: opt6[e[i].first.first]) {
if(x.second == i) {
continue;
}
pt2 = min(pt2, rev1[e[i].first.first][x.first.first] + x.first.second);
break;
}
backward = min(backward, pt1 + pt2);
ans = min(ans, forward + backward + e[i].second.second);
//cout << "flip pair<pair<int,int>,pair<int,int> > " << i << ": " << forward << " + " << backward << " + " << e[i].second.second << " = " << forward + backward + e[i].second.second << "\n";
}
cout << (ans <= 1e12 ? ans : -1) << "\n";
}
/*
5 6
1 2 1 10000
2 5 1 10000
5 3 1 10000
2 3 10 1
2 4 1 10000
4 1 1 10000
2 2
1 2 3 4
1 2 3 9
3 4
1 2 3 4
2 3 3 9
2 1 3 10
2 3 3 11
2 7
1 2 1 1
1 2 1 7
1 2 1 3
1 2 1 4
1 2 1 5
1 2 1 6
1 2 1 9
*/
