#include <bits/stdc++.h>
#define d1(x) cout << #x << " : " << x << endl << flush
#define d2(x, y) cout << #x << " : " << x << " " << #y << " : " << y << endl << flush
#define d3(x, y, z) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << endl << flush
#define d4(x, y, z, a) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << " "<< #a << " : " << a << endl << flush
#define arr(x) array <ll, x>
#define ld long double
#define ll long long
#define int long long
#define pb push_back
#define endl '\n'
#define lc v << 1
#define rc v << 1 | 1
using namespace std;
const int INF = 1e14 + (35 / 10); // 35 ---> 36
const int MAXN = 2e5 + (35 / 10); // 35 ---> 36
vector <arr(5)> adj[MAXN];
vector <int> dp[MAXN];
map <arr(2), int> mp;
int C[MAXN], P[MAXN];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++)
dp[i].pb(INF);
for(int i = 1; i <= m; i++){
int u, v, c, p;
cin >> u >> v >> c >> p;
C[i] = c;
P[i] = p;
u--;
v--;
int eli = adj[u].size();
int esi = adj[v].size();
adj[u].pb({v, c, p, esi + 1, i});
adj[v].pb({u, c, p, eli + 1, i});
dp[u].pb(INF);
dp[v].pb(INF);
mp[{u, c}] += p;
mp[{v, c}] += p;
}
for(int i = 0; i <= adj[0].size(); i++)
dp[0][i] = 0;
dp[0][0] = 0;
set <arr(4)> s;
s.insert({0, 0, 0});
while(!s.empty()){
auto [w, u, cool, id] = *s.begin();
s.erase(s.begin());
// d4(w, u, cool, C[id]);
for(int i = 0; i < adj[u].size(); i++){
auto [v, c, p, ind, ID] = adj[u][i];
int cost = p;
if(dp[v][0] > w + cost){
dp[v][0] = w + cost;
s.insert({dp[v][0], v, 0, ID});
// d3(dp[v][0], v, c);
}
if(cool != c){
cost = mp[{u, c}] - p;
if(cool == 0 && C[id] == c)
cost -= P[id];
if(dp[v][ind] > w + cost){
dp[v][ind] = w + cost;
s.insert({dp[v][ind], v, c, ID});
// d4(dp[v][ind], v, c, p);
}
}
// d3(i, u, v);
// d1(2);
}
// d1(u);
// cout << endl;
}
// cout << mp[{1, 3}] << " " << mp[{3, 3}] << endl;
int ans = INF;
for(auto u : dp[n - 1])
ans = min(ans, u);
if(ans == INF)
ans = -1;
cout << ans << endl;
}
// Ey To Bahane! :_)))
// -------------<3------------- //
/*
Magasan dor shirini:
1. MAXN
2. Input style
3. index or value? Masale In Ast!
4. MOD
*/
