#include<bits/stdc++.h>
using namespace std;
template <class A, class B>
bool mini(A &a, const B b) {
if(a > b){
a = b;
return true;
}
return false;
}
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a.size())
typedef pair <int, int> pii;
typedef long long ll;
typedef vector <int> vi;
const int N = 3e5 + 5;
const int oo = 2e9;
const int MOD = 1e9 + 7;
const long long INF = 1e18;
int n, m;
vector <array <int, 3>> g[N];
array <int, 4> E[N];
struct Data{
int u, t;
long long cost;
bool operator <(const Data &x) const{
return cost > x.cost;
}
}; priority_queue <Data, vector <Data>> pq;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define taskname "r25robot12"
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
cin >> n >> m;
vector <map <int, long long>> sum_c(n + 2);
vector <map <int, long long>> dp(n + 2);
FOR(i, 1, m){
int u, v, c, p; cin >> u >> v >> c >> p;
g[u].push_back({c, v, p}); g[v].push_back({c, u, p});
sum_c[u][c]+= p;
sum_c[v][c]+= p;
E[i] = {u, v, c, p};
}
dp[1][0] = 0;
pq.push({1, 0, 0});
FOR(i, 1, n) sort(g[i].begin(), g[i].end());
while(!pq.empty()){
auto [u, t, cost] = pq.top();
pq.pop();
if(cost != dp[u][t]) continue;
if(t == 0){
for(auto [c, v, p] : g[u]){
if(!dp[v].count(c)) dp[v][c] = 1e18;
if(!dp[v].count(0)) dp[v][0] = 1e18;
if(t == 0){
if(dp[v][0] > cost + min(1LL * sum_c[u][c] - p, 1LL * p)){
dp[v][0] = cost + min(1LL * sum_c[u][c] - p, 1LL * p);
pq.push({v, 0, dp[v][0]});
}
if(dp[v][c] > cost){
dp[v][c] = cost;
pq.push({v, c, dp[v][c]});
}
}
}
} else{
for(auto it = lower_bound(g[u].begin(), g[u].end(), array <int, 3> {t, 0, 0}); it != g[u].end(); it++){
auto [c, v, p] = *it;
if(c != t) break;
if(!dp[v].count(0)) dp[v][0] = 1e18;
if(dp[v][0] > cost + sum_c[u][c] - p){
dp[v][0] = cost + sum_c[u][c] - p;
pq.push({v, 0, dp[v][0]});
}
}
}
}
if(dp[n].count(0) == 0 || dp[n][0] == 1e18) cout << - 1;
else cout << dp[n][0];
return 0;
}
