#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
struct edge {
int v,pos,c,cost;
edge(){}
edge(int _v, int _pos, int _c, int _cost) {
v = _v;
pos = _pos;
c = _c;
cost = _cost;
}
};
const int N = 1e5 + 5;
const int M = 2e5 + 5;
const long long oo = 1e18;
vector <edge> adj[N];
vector <long long> dis[N];
long long sum[M];
int n,m;
template <typename T>
bool mini(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u,v,c,w;
cin >> u >> v >> c >> w;
edge a = edge(v, adj[v].size(), c, w);
edge b = edge(u, adj[u].size(), c, w);
adj[u].push_back(a);
adj[v].push_back(b);
}
for (int i = 1; i <= n; i++)
dis[i].assign(adj[i].size() + 1, oo);
priority_queue <pair <long long, pair <int, int>>> heap;
heap.push(mp(0, mp(1, adj[1].size())));
dis[1][adj[1].size()] = 0;
while (heap.size()) {
int u = heap.top().se.fi;
int id = heap.top().se.se;
long long cur = -heap.top().fi;
heap.pop();
if (cur != dis[u][id])
continue;
//cerr << u << " " << id << endl;
for (int i = 0; i < (int) adj[u].size(); i++) if (i != id) {
edge e = adj[u][i];
sum[e.c] += e.cost;
}
for (int i = 0; i < (int) adj[u].size(); i++) if (i != id) {
edge e = adj[u][i];
int v = e.v;
int c = e.c;
int pos = e.pos;
int cost = e.cost;
if (mini(dis[v][pos], cur + cost))
heap.push(mp(-dis[v][pos], mp(v, pos)));
if (mini(dis[v][adj[v].size()], cur + sum[c] - cost))
heap.push(mp(-dis[v][adj[v].size()], mp(v, adj[v].size())));
}
for (edge e : adj[u])
sum[e.c] = 0;
}
long long ans = oo;
for (long long res : dis[n])
ans = min(ans, res);
if (ans == oo)
ans = -1;
cout << ans;
return 0;
}
