#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Edge {
ll a, b, c, d;
};
ll n, m;
ll M = 210, inf = 1e18;
vector<vector<ll>> g(M), gt(M), dist(M, vector<ll>(M, inf));
vector<Edge> e;
void floyd() {
for(int k=1; k<=n; ++k) {
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i=1; i<=n; ++i) dist[i][i] = 0;
for(ll i=0; i<m; ++i) {
Edge x;
cin >> x.a >> x.b >> x.c >> x.d;
dist[x.a][x.b] = min(dist[x.a][x.b], x.c);
g[x.a].push_back(i);
gt[x.b].push_back(i);
e.emplace_back(x);
}
floyd();
ll ans = dist[1][n] + dist[n][1];
for(auto[a, b, c, d] : e) {
ans = min(ans, dist[1][b] + c + d + dist[a][n] + dist[n][1]);
ans = min(ans, dist[1][n] + c + d + dist[n][b] + dist[a][1]);
}
if(ans >= inf) cout << "-1\n";
else cout << ans << "\n";
return 0;
}
