#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v, c, p;
int other( int w ) {
return u ^ v ^ w;
}
};
struct elemPQ {
int u;
long long d;
bool operator < ( const elemPQ &x ) const {
return x.d < d;
}
};
const int MAX_N = 1e5;
const int MAX_M = 2e5;
const long long INF = 1e18;
bool vis[MAX_N + 1];
long long dist[MAX_N + 1];
edge edges[MAX_M + 1];
vector<int> adj[MAX_N + 1];
unordered_map<int, int> maxEdge[MAX_N + 1], maxEdge2[MAX_N + 1];
unordered_map<int, long long> sumColor[MAX_N + 1];
priority_queue<elemPQ> pq;
int main() {
int n, m;
cin >> n >> m;
for ( int e = 1; e <= m; e++ ) {
cin >> edges[e].u >> edges[e].v >> edges[e].c >> edges[e].p;
adj[edges[e].u].push_back( e );
adj[edges[e].v].push_back( e );
}
for ( int v = 1; v <= n; v++ ) {
dist[v] = INF;
for ( int e: adj[v] ) {
int c = edges[e].c, p = edges[e].p;
sumColor[v][c] += p;
if ( p > edges[maxEdge[v][c]].p ) {
maxEdge2[v][c] = maxEdge[v][c];
maxEdge[v][c] = e;
} else if ( p > edges[maxEdge2[v][c]].p )
maxEdge2[v][c] = e;
}
}
dist[1] = 0;
pq.push( { 1, dist[1] } );
while ( !pq.empty() ) {
int u = pq.top().u;
pq.pop();
//printf( "%d %lld\n", u, dist[u] );
if ( vis[u] )
continue;
vis[u] = true;
for ( int e: adj[u] ) {
int v = edges[e].other( u ), c = edges[e].c, p = edges[e].p;
if ( dist[u] + p < dist[v] ) {
dist[v] = dist[u] + p;
pq.push( { v, dist[v] } );
}
if ( dist[u] + sumColor[u][c] - p < dist[v] ) {
dist[v] = dist[u] + sumColor[u][c] - p;
pq.push( { v, dist[v] } );
}
int f = 0;
if ( maxEdge[v][c] == e )
f = maxEdge2[v][c];
else
f = maxEdge[v][c];
if ( f != 0 ) {
int w = edges[f].other( v );
if ( dist[u] + sumColor[v][c] - edges[f].p < dist[w] ) {
dist[w] = dist[u] + sumColor[v][c] - edges[f].p;
pq.push( { w, dist[w] } );
}
}
}
}
cout << (dist[n] == INF ? -1 : dist[n]) << "\n";
return 0;
}
