#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const ll inf = 1e17;
const int N = 100'010;
map<int, ll> sum[N];
map<int, vector<pll>> colA[N];
map<int, ll> dis[N];
vector<tuple<int,int,ll,ll>> A[N];
int n, m;
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,m) {
int v, u, c, w;
cin >> v >> u >> c >> w;
--v; --u;
A[v].push_back({u,c,w,0});
A[u].push_back({v,c,w,0});
sum[v][c] += w;
sum[u][c] += w;
}
Loop (v,0,n) {
for (auto &[u, c, w1, w2] : A[v]) {
w2 = sum[v][c] - w1;
colA[v][c].push_back({u,w2});
dis[v][c] = inf;
}
dis[v][-1] = inf;
}
set<tuple<ll,int,int>> s = {{0, -1, 0}};
dis[0][-1] = 0;
while (s.size()) {
auto [d, c, v] = *s.begin();
s.erase(s.begin());
if (c == -1) {
for (auto [u, c, w1, w2] : A[v]) {
ll w = min(w1, w2);
if (d + w < dis[u][-1]) {
s.erase({dis[u][-1], -1, u});
dis[u][-1] = d+w;
s.insert({dis[u][-1], -1, u});
}
if (d < dis[u][c]) {
s.erase({dis[u][c], c, u});
dis[u][c] = d;
s.insert({dis[u][c], c, u});
}
}
} else {
for (auto [u, w] : colA[v][c]) {
if (d + w < dis[u][-1]) {
s.erase({dis[u][-1], -1, u});
dis[u][-1] = d+w;
s.insert({dis[u][-1], -1, u});
}
}
}
}
cout << (dis[n-1][-1] == inf? -1: dis[n-1][-1]) << '\n';
}
