#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int LIM = 1e5, INF = 1e18;
class comp{
public:
bool operator()(array<int, 3> &x, array<int, 3> &y){ return x[0] > y[0]; }
};
map<int, int> d[LIM], s[LIM];
map<int, vector<array<int, 2>>> g[LIM];
priority_queue<array<int, 3>, vector<array<int, 3>>, comp> 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 + min(s[u][h.first] - w, w), 0);
add(v, dist, h.first);
}
}
}
cout << (d[n-1][0] == INF ? -1 : d[n-1][0]);
}
