#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int dis[205][205];
array<int, 4> Edge[50005];
vector<array<int, 3>> adj1[205], adj2[205];
int dist[205];
bool vis[205];
int adj[205][205];
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
int i, j;
clock_t st = clock();
for(i=0;i<N;i++) {
for(j=0;j<N;j++) dis[i][j] = INF;
dis[i][i] = 0;
}
for(i=0;i<M;i++) {
int a, b, c, d;
//a = rand()%N+1, b = rand()%N+1, c = rand(), d = rand();
cin >> a >> b >> c >> d;
Edge[i] = {a-1, b-1, c, d};
dis[a-1][b-1] = min(dis[a-1][b-1], c);
}
for(int k = 0; k < N; k++) {
for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
for(i=0;i<M;i++) {
adj1[Edge[i][0]].push_back({Edge[i][1], i});
adj2[Edge[i][1]].push_back({Edge[i][0], i});
}
set<int> S;
for(i=0;i<N;i++) dist[i] = INF;
for(i=0;i<N;i++) vis[i] = false;
dist[0] = 0;
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int,2>>> PQ;
PQ.push({0, 0});
while(!PQ.empty()) {
auto k = PQ.top();
PQ.pop();
int id = k[1];
if(vis[id]) continue;
vis[id] = true;
for(auto n : adj1[id]) {
if(dist[n[0]] > dist[id] + Edge[n[1]][2]) {
dist[n[0]] = dist[id] + Edge[n[1]][2];
PQ.push({dist[n[0]], n[0]});
}
}
}
int pt = N-1;
if(dist[N-1]!=INF) {
while(pt != 0) {
int prv = pt;
for(auto n : adj2[pt]) {
if(pt == n[0]) continue;
if(dist[n[0]] + Edge[n[1]][2] == dist[pt]) {
S.insert(n[1]);
pt = n[0];
break;
}
}
assert(pt != prv);
}
}
for(i=0;i<N;i++) dist[i] = INF;
for(i=0;i<N;i++) vis[i] = false;
dist[N-1] = 0;
PQ = priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int,2>>> {};
PQ.push({0, N-1});
while(!PQ.empty()) {
auto k = PQ.top();
PQ.pop();
int id = k[1];
if(vis[id]) continue;
vis[id] = true;
for(auto n : adj1[id]) {
if(dist[n[0]] > dist[id] + Edge[n[1]][2]) {
dist[n[0]] = dist[id] + Edge[n[1]][2];
PQ.push({dist[n[0]], n[0]});
}
}
}
pt = 0;
if(dist[0]!=INF) {
while(pt != N-1) {
int prv = pt;
for(auto n : adj2[pt]) {
if(pt == n[0]) continue;
if(dist[n[0]] + Edge[n[1]][2] == dist[pt]) {
S.insert(n[1]);
pt = n[0];
break;
}
}
assert(pt != prv);
}
}
return 0;
int mi = dis[0][N-1] + dis[N-1][0];
for(i=0;i<M;i++) {
if(S.find(i) != S.end()) continue;
int val = Edge[i][3];
int d1 = dis[0][N-1], d2 = dis[N-1][0];
int a = Edge[i][0], b = Edge[i][1], c = Edge[i][2];
d1 = min(d1, dis[0][b] + c + dis[a][N-1]);
d2 = min(d2, dis[N-1][b] + c + dis[a][0]);
mi = min(mi, val + d1 + d2);
//cout << i << " : " << val << ' ' << d1 << ' ' << d2 << '\n';
}
assert(S.size() < 2*N);
for(int n : S) {
int val = Edge[n][3];
for(i=0;i<N;i++) {
for(j=0;j<N;j++) adj[i][j] = INF;
adj[i][i] = 0;
}
for(i=0;i<M;i++) {
if(i==n) {
adj[Edge[i][1]][Edge[i][0]] = min(adj[Edge[i][1]][Edge[i][0]], Edge[i][2]);
}
else adj[Edge[i][0]][Edge[i][1]] = min(adj[Edge[i][0]][Edge[i][1]], Edge[i][2]);
}
for(i=0;i<N;i++) vis[i] = false;
for(i=0;i<N;i++) dist[i] = INF;
dist[0] = 0;
while(true) {
int mi = INF, pt = -1;
for(i=0;i<N;i++) {
if(!vis[i] && mi > dist[i]) {
mi = dist[i];
pt = i;
}
}
if(pt == -1) break;
vis[pt] = true;
for(i=0;i<N;i++) {
if(dist[i] > dist[pt] + adj[pt][i]) {
dist[i] = dist[pt] + adj[pt][i];
}
}
}
if(dist[N-1]==INF) continue;
val += dist[N-1];
for(i=0;i<N;i++) vis[i] = false;
for(i=0;i<N;i++) dist[i] = INF;
dist[N-1] = 0;
while(true) {
int mi = INF, pt = -1;
for(i=0;i<N;i++) {
if(!vis[i] && mi > dist[i]) {
mi = dist[i];
pt = i;
}
}
if(pt == -1) break;
vis[pt] = true;
for(i=0;i<N;i++) {
if(dist[i] > dist[pt] + adj[pt][i]) {
dist[i] = dist[pt] + adj[pt][i];
}
}
}
if(dist[0]==INF) continue;
val += dist[0];
mi = min(mi, val);
}
cout << (mi <= 1e17 ? mi : -1);
//cout << '\n' << clock() - st <<"ms";
}
