//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
const int N = 101000;
const int M = 401000;
int n, m, a, b, c, p, l;
int kr[M];
int cost[M];
int color[M];
map<int, vector<int>> mp[N];
long long odl[M][2]; // którą krawędzią przyszliśmy | czy zmieniliśmy jej kolor
priority_queue<pair<long long, pair<int, int>>> pq;
int main() {
l = 1;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d%d", &a, &b, &c, &p);
++l;
kr[l] = b;
cost[l] = p;
color[l] = c;
mp[a][c].push_back(l);
odl[l][0] = 1e18;
odl[l][1] = 1e18;
//~ debug(l, a, b, c, p);
++l;
kr[l] = a;
cost[l] = p;
color[l] = c;
mp[b][c].push_back(l);
odl[l][0] = 1e18;
odl[l][1] = 1e18;
//~ debug(l, b, a, c, p);
}
kr[0] = 1;
pq.push({0, {0, 0}});
while (!pq.empty()) {
long long w = -pq.top().first;
int x = pq.top().second.first;
int y = pq.top().second.second;
pq.pop();
//~ debug(w, x, y);
if (kr[x] == n) {
printf("%lld\n", odl[x][y]);
return 0;
}
if (odl[x][y] != w) {
continue;
}
for (auto i : mp[kr[x]]) {
//~ debug(i);
long long sum = 0;
for (int j : i.second) {
if ((j ^ 1) != x || (y == 0)) {
sum += cost[j];
}
}
//~ debug(sum);
for (int j : i.second) {
if ((j ^ 1) == x && (y == 1)) {
continue;
}
if (odl[j][0] > w + sum - cost[j]) {
odl[j][0] = w + sum - cost[j];
pq.push({-odl[j][0], {j, 0}});
}
if (odl[j][1] > w + cost[j]) {
odl[j][1] = w + cost[j];
pq.push({-odl[j][1], {j, 1}});
}
}
}
}
printf("-1\n");
return 0;
}
