#include <bits/stdc++.h>
// #ifdef DEBUG
// #define D(..) = printf(..)
// #else
// #define D(..) = printf(..)
// #endif
using namespace std;
int n,m;
typedef long long ll;
typedef pair<ll, ll> pll;
// price, target
map<int,vector<pll>> g[100005];
map<int,ll> tc[100005];
/// final graph to dijkstra over
vector<pll> fg[100005];
// Observations: You want to reach each node at most once
// You can always assign a new unique edge
// At each node you have two choices: Assign every other edge, and take the edge for free,
// or just assign
inline void add_edge(int u, int v, int c, long long p){
if (g[u].find(c) == g[u].end()){
vector<pll> vec;
vec.push_back({p,v});
g[u][c] = vec;
tc[u][c] = p;
}
else{
g[u][c].push_back({p,v});
tc[u][c] += p;
}
}
inline void add_change_edge(int u, int v, int c, long long p){
// Add edge from u -> v
fg[u].push_back({v,p});
// printf("Added change base %d-%lld %lld\n", u, v, p);
// I'm pretty sure you only need to consider the top 2 weights, but the math seems ab it tight and
// idk if I have all the cases considered
// ll maxw = g[u][c][0].first;
for (int i = 0; i < min(4,(int) g[v][c].size()); i++){
ll tgt = g[v][c][i].second;
ll w = g[v][c][i].first;
if (tgt == u){
continue; // don't do a back-edge
}
// New edge: Go from u to v to tgt, where we change u -> v, and don't change v -> tgt
fg[u].push_back({tgt, tc[v][c] - w});
// printf("Added change case %d-%lld %lld\n", u, tgt, tc[v][c] - w);
}
}
ll dist[100005];
bool explored[100005];
priority_queue<pll,vector<pll>,greater<pll>> q;
int main(){
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++){
int u,v,c;
long long p;
scanf("%d %d %d %lld", &u,&v,&c,&p);
add_edge(u,v,c,p);
add_edge(v,u,c,p);
}
for (int i = 1; i <= n; i++){
dist[i] = 1e18;
// sort the vecs
for (auto cur : g[i]){
int c = cur.first;
sort(g[i][c].begin(),g[i][c].end(), greater<pll>());
}
}
for (int i = 1; i <= n; i++){
for (auto cur : g[i]){
int c = cur.first;
for (auto thing : cur.second){
ll v = thing.second;
ll p = thing.first;
add_change_edge(i,v,c,p);
fg[i].push_back({v,tc[i][c] - p});
// printf("%lld %lld %lld\n", i, v , p);
}
}
}
// for (int i = 1; i <= n; i++){
// for (auto tgt : fg[i]){
// }
// }
dist[1] = 1;
q.push({0,1});
while (!q.empty()){
auto cur = q.top();
q.pop();
long long d = cur.first;
long long x = cur.second;
if (explored[x]){
continue;
}
explored[x] = true;
for (auto tgt : fg[x]){
ll tdist = tgt.second + d;
if (!explored[tgt.first] && tdist < dist[tgt.first]){
q.push({tdist,tgt.first});
dist[tgt.first] = tdist;
}
}
}
if (dist[n] > 9e17){
printf("-1\n");
}
else{
printf("%lld\n", dist[n]);
}
}
