#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v, c, d;
};
struct vd {
int v, d;
bool operator < ( const vd &x ) const {
return d > x.d;
}
};
const int MAX_N = 200;
const int MAX_M = 5e4;
const int INF = 1e9;
int n;
bool vis[MAX_N + 1], used[MAX_N + 1][MAX_N + 1], usedNew[MAX_N + 1];
int dist[MAX_N + 1][MAX_N + 1], distNew[MAX_N + 1], parent[MAX_N + 1];
vector<int> adjIn[MAX_N + 1], adjOut[MAX_N + 1];
edge edges[MAX_M];
int specialEdge;
void getDistances( int s, int t, int dist[], bool used[] ) {
for ( int v = 1; v <= n; v++ )
dist[v] = INF, vis[v] = false;
priority_queue<vd> pq;
dist[s] = 0;
pq.push( { s, dist[s] } );
while ( !pq.empty() ) {
int u = pq.top().v;
pq.pop();
if ( vis[u] )
continue;
vis[u] = true;
for ( int e: adjOut[u] ) {
int v = edges[e].v, c = edges[e].c;
if ( e == specialEdge ) {
if ( u == edges[e].v )
v = edges[e].u;
else
continue;
}
if ( dist[u] + c < dist[v] ) {
dist[v] = dist[u] + c;
parent[v] = e;
pq.push( { v, dist[v] } );
}
}
}
if ( dist[t] != INF ) {
int v = t;
while ( v != s ) {
int e = parent[v];
used[e] = true;
v = edges[e].u;
if ( e == specialEdge )
v = edges[e].v;
}
}
}
int main() {
int m;
cin >> n >> m;
for ( int e = 0; e < m; e++ ) {
cin >> edges[e].u >> edges[e].v >> edges[e].c >> edges[e].d;
adjOut[edges[e].u].push_back( e );
adjIn[edges[e].v].push_back( e );
}
specialEdge = -1;
for ( int s = 1; s <= n; s++ ) {
int t = (s == 1 ? n : 1);
getDistances( s, t, dist[s], used[s] );
}
int minTotalCost = dist[1][n] + dist[n][1];
//printf( "0 durmuri: \n", dist[1][n] + dist[n][1] );
for ( int e = 0; e < m; e++ ) {
int u = edges[e].u, v = edges[e].v, c = edges[e].c;
int newCost1N, newCostN1;
//if ( !used[1][e] )
//newCost1N = min( dist[1][n], dist[1][v] + c + dist[u][n] );
//else {
specialEdge = e;
adjOut[v].push_back( e );
getDistances( 1, n, distNew, usedNew );
newCost1N = distNew[n];
adjOut[v].pop_back();
//}
//if ( !used[n][e] )
//newCostN1 = min( dist[n][1], dist[n][v] + c + dist[u][1] );
//else {
specialEdge = e;
adjOut[v].push_back( e );
getDistances( n, 1, distNew, usedNew );
newCostN1 = distNew[1];
adjOut[v].pop_back();
// }
//printf( "drumul %d: %d %d %d\n", e, newCost1N, newCostN1, newCost1N + newCostN1 + edges[e].d );
minTotalCost = min( minTotalCost, newCost1N + newCostN1 + edges[e].d );
}
cout << (minTotalCost >= INF ? - 1 : minTotalCost) << "\n";
}
