#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int LIM = 1e5, INF = 2e9;
int n, m, a[4][2*LIM], d[5*LIM];
vector<array<int, 2>> g[LIM];
unordered_map<int, int> s[LIM];
priority_queue<array<int, 2>> q;
void add(int i, int j){
if(d[i] > j) q.push({-(d[i] = j), i});
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<m; ++i){
for(int j=0; j<4; ++j) cin >> a[j][i];
--a[0][i], --a[1][i];
g[a[0][i]].push_back({a[1][i], i});
g[a[1][i]].push_back({a[0][i], i});
s[a[0][i]][a[2][i]] += a[3][i];
s[a[1][i]][a[2][i]] += a[3][i];
}
fill(d, d+n+m*2, INF);
q.push({d[0] = 0, 0});
int ans = INF;
while(!q.empty()){
int dist = -q.top()[0], u = q.top()[1]; q.pop();
if(dist != d[u]) continue;
if(u < n){
for(auto &[v, e] : g[u]){
add(n+e+m*(u == a[0][e]), dist + a[3][e]);
add(v, dist + s[u][a[2][e]] - a[3][e]);
}
}else{
int f = (u -= n) % m;
u = a[u >= m][f];
if(u == n-1) ans = min(ans, dist);
for(auto &[v, e] : g[u]){
add(n+e+m*(u == a[0][e]), dist + a[3][e]);
if(a[2][e] != a[2][f])
add(v, dist + s[u][a[2][e]] - a[3][e]);
else if(e - f)
add(v, dist + s[u][a[2][e]] - a[3][e] - a[3][f]);
}
}
}
ans = min(ans, d[n-1]);
cout << (ans == INF ? -1 : ans);
}
