// Src : Vux2Code
/* Note :
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front
#define vec3d vector<vector<vector<ll>>>
#define vec2d vector<vector<ll>>
#define vec1d vector<ll>
vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}
// debug (+20)
#define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)
template<typename... Args>
void debug_impl(const char* names, Args&&... args) {
vector<string> _names;
{
istringstream ss(names);
string token;
while (getline(ss, token, ',')) {
auto l = token.find_first_not_of(" \t");
auto r = token.find_last_not_of(" \t");
if (l == string::npos) _names.push_back("");
else _names.push_back(token.substr(l, r - l + 1));
}
}
cerr << "(";
size_t _i = 0;
int _dummy[] = { 0, ((cerr << _names[_i] << " : " << args << (++_i < _names.size() ? ", " : "")), 0)... };
(void)_dummy;
cerr << ")" << endl;
}
// Triple (+12)
struct tri {
ll fi, se, th;
tri(ll _fi, ll _se, ll _th) : fi(_fi), se(_se), th(_th) {}
bool operator<(const tri& o) const {
if (fi != o.fi) return fi < o.fi;
if (se != o.se) return se < o.se;
return th < o.th;
}
bool operator>(const tri& o) const {
return o < *this;
}
};
template<typename T>
using rvs_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
#define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
#define foreach(i, j) for (ll i : (j))
#define all(a) (a).begin (), (a). end ()
#define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())
const ll maxN = 1e6 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;
void maxi(ll &x, ll y) { x = max(x, y); }
void mini(ll &x, ll y) { x = min(x, y); }
/* ---------HASHING-------- */
// const base = 31, mod2 = 1e9 + 9;
/* ---------BITMASK-------- */
// ll count(ll x) { return __builtin_popcountll(x); }
// ll fst(ll x) { return 63 - __builtin_clzll(x); }
// ll last(ll x) { return __builtin_ctzll(x); }
// bool bit(ll x, ll y) { return ((x >> y) & 1); }
ll t = 1;
ll n, m;
map <ll, vector <tri>> adj [maxN];
rvs_pq <tri> q;
map <ll, ll> dis [maxN], sum [maxN];
void ck (ll x, ll y, ll val) {
if (dis [x]. find (y) == dis [x]. end () || dis [x] [y] > val) {
dis [x] [y] = val;
q. push ({val, x, y});
}
}
void solve() {
cin >> n >> m;
forinc (i, 1, m) {
ll a, b, c, p;
cin >> a >> b >> c >> p;
adj [a] [c]. pusb ({b, c, p});
adj [b] [c]. pusb ({a, c, p});
sum [a] [c] += p;
sum [b] [c] += p;
}
dis [1] [0] = 0;
q. push ({dis [1] [0], 1, 0});
while (!q. empty ()) {
ll d = q. top (). fi;
ll id = q. top (). se;
ll c = q. top (). th;
q. pop ();
if (dis [id] [c] != d) continue;
// cerr << id << ' ' << c << ' ' << d << '\n';
if (c == 0) {
for (auto &i : adj [id]) {
for (auto &e : i. se) {
ll v = e.fi, color = e.se, price = e.th;
ck(v, 0, d + sum[id][color] - price);
ck(v, 0, d + price);
ck(v, color, d);
}
}
} else {
for (auto &e : adj[id][c]) {
ll v = e.fi, price = e.th;
ck(v, 0, d + sum[id][c] - price);
}
}
}
// forinc (i, 1, n) {
// cerr << i << '\n';
// for (pll j : dis [i]) {
// cerr << j. fi << ' ' << j. se << '\n';
// }
// }
cout << (dis [n]. find (0) == dis [n]. end () ? -1 : dis [n] [0]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// #define TASK "E:/Code/CP/task"
// if (fopen (TASK".inp", "r")) {
// freopen (TASK".inp", "r", stdin);
// freopen (TASK".out", "w", stdout);
// }
// cin >> t;
while (t--) solve();
}
