#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int LIM = 1e5, INF = 1e18;
map<int, int> d[LIM], s[LIM];
map<int, vector<array<int, 2>>> g[LIM];
priority_queue<array<int, 3>> q;
void add(int i, int j, int k){
if(d[i][k] > j) q.push({-(d[i][k] = j), i, k});
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
for(int i=0; i<m; ++i){
int u, v, c, w; cin >> u >> v >> c >> w;
--u, --v;
g[u][c].push_back({v, w});
g[v][c].push_back({u, w});
s[u][c] += w;
s[v][c] += w;
d[u][c] = d[v][c] = INF;
}
for(int u=0; u<n; ++u) d[u][0] = INF;
q.push({d[0][0] = 0, 0});
while(!q.empty()){
int dist = -q.top()[0], u = q.top()[1], c = q.top()[2];
q.pop();
if(dist != d[u][c]) continue;
if(c){
for(auto &[v, w] : g[u][c])
if(s[u][c] - w >= 0)
add(v, dist + s[u][c] - w, 0);
}else{
for(auto &h : g[u])
for(auto &[v, w] : h.second){
add(v, dist + w, 0);
add(v, dist + s[u][h.first] - w, 0);
add(v, dist, h.first);
}
}
}
cout << (d[n-1][0] == INF ? -1 : d[n-1][0]);
}
