#include <bits/stdc++.h>
#define int long long
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 = 2e15;
int n;
bool vis[MAX_N + 1], used1[MAX_M + 1], usedN[MAX_M + 1], usedNew[MAX_M + 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 && v == u )
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;
}
}
}
signed 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;
getDistances( 1, n, dist[1], used1 );
getDistances( n, 1, dist[n], usedN );
for ( int u = 1; u <= n; u++ ) {
for ( int v = 1; v <= n; v++ )
dist[u][v] = INF;
}
for ( int u = 1; u <= n; u++ )
dist[u][u] = 0;
for ( int e = 0; e < m; e++ )
dist[edges[e].u][edges[e].v] = edges[e].c;
for ( int w = 1; w <= n; w++ ) {
for ( int u = 1; u <= n; u++ ) {
for ( int v = 1; v <= n; v++ )
dist[u][v] = min( dist[u][v], dist[u][w] + dist[w][v] );
}
}
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;
unsigned newCost1N, newCostN1;
//if ( !used1[e] )
// newCost1N = min( dist[1][n], dist[1][v] + c + dist[u][n] );
//else {
specialEdge = e;
adjOut[v].push_back( e );
swap( edges[e].u, edges[e].v );
getDistances( 1, n, distNew, usedNew );
newCost1N = distNew[n];
swap( edges[e].u, edges[e].v );
adjOut[v].pop_back();
//}
//if ( !usedN[e] )
// newCostN1 = min( dist[n][1], dist[n][v] + c + dist[u][1] );
//else {
specialEdge = e;
adjOut[v].push_back( e );
swap( edges[e].u, edges[e].v );
getDistances( n, 1, distNew, usedNew );
newCostN1 = distNew[1];
swap( edges[e].u, edges[e].v );
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";
}
