#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,long long>;
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
void solve(){
int n, m;
cin >> n >> m;
map<int, vector<array<long long,3>>> graph[n + 1];
map<int, ll> psum[n + 1];
map<int, ll> dp2[n + 1];
vector<ll> dp(n + 1, 1e18);
REP(i, m){
int u, v, c;
ll p;
cin >> u >> v >> c >> p;
graph[u][c].pb({v, c, p});
graph[v][c].pb({u, c, p});
psum[u][c] += p;
psum[v][c] += p;
}
using T = array<long long, 3>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, 1, 0});
dp[1] = 0;
while(pq.size()){
auto [val, u, cur] = pq.top();
pq.pop();
if (cur){
if (dp2[u][cur] != val) continue;
for (auto [to, c, p] : graph[u][cur]){
ll case1 = psum[u][c] - p;
if (val + case1 < dp[to]){
dp[to] = val + case1;
pq.push({dp[to], to, 0});
}
}
}
else{
if (dp[u] != val) continue;
for (auto color : graph[u]){
for (auto [to, c, p] : color.se){
ll case1 = psum[u][c] - p + val;
if (case1 < dp[to]){
dp[to] = case1;
pq.push({case1, to, 0});
}
ll case2 = p + val;
if (case2 < dp[to]){
dp[to] = case2;
pq.push({case2, to, 0});
}
ll case3 = val;
if (!dp2[to].count(c) || case3 < dp2[to][c]){
dp2[to][c] = case3;
pq.push({case3, to, c});
}
}
}
}
}
cout << (dp[n] == 1e18 ? -1 : dp[n]);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tests = 1;
// cin >> tests;
for (int _ = 1; _ <= tests; _++){
cerr << "- Case #" << _ << ": \n";
solve();
el;
}
return 0;
}
