#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int LIM = 1e5, INF = 1e18;
int n, m, a[4][2*LIM], d[5*LIM];
map<int, vector<array<int, 2>>> g[LIM];
map<int, int> s[LIM];
map<int, bool> vis[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]][a[2][i]].push_back({a[1][i], i});
g[a[1][i]][a[2][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){
int f = (u -= n) % m;
u = a[u >= m][f];
if(!vis[u][a[2][f]]){
for(auto &[v, e] : g[u][a[2][f]])
if(e != f)
add(v, dist + s[u][a[2][e]] - a[3][e]);
vis[u][a[2][f]] = 1;
}
if(u == n-1) ans = min(ans, dist + a[3][f]);
}else{
if(!vis[u][0]){
for(auto &[z, h] : g[u]){
for(auto &[v, e] : h){
add(v, dist + min(s[u][a[2][e]] - a[3][e], a[3][e]));
add(n+e+m*(u == a[0][e]), dist);
}
}
vis[u][0] = 1;
}
if(u == n-1) ans = min(ans, dist);
}
}
cout << (ans == INF ? -1 : ans);
}
