#include<bits/stdc++.h>
using namespace std;
vector<pair<long long,pair<long long,long long>>> g[220000];
map<long long,vector<pair<long long,long long>>> gc[220000];
map<long long,long long> d[220000], sm[220000];
int32_t main() {
long long n, m; cin >> n >> m;
for(long long i = 1; i <= m; i++) {
long long u, v, c, w; cin >> u >> v >> c >> w;
g[u].push_back(make_pair(v,make_pair(c,w)));
g[v].push_back(make_pair(u,make_pair(c,w)));
}
for(long long i = 1; i <= n; i++) {
d[i][0] = 1000000000000000010;
for(auto V : g[i]) {
d[i][V.second.first] = 1000000000000000010;
gc[i][V.second.first].push_back(make_pair(V.first,V.second.second));
sm[i][V.second.first]+= V.second.second;
}
}
priority_queue<pair<long long,pair<long long,long long>>> pq;
pq.push(make_pair(0,make_pair(1,0))); d[1][0] = 0;
while(pq.size()) {
long long u = pq.top().second.first;
long long dist = -pq.top().first;
long long cl = pq.top().second.second;
pq.pop();
if(dist != d[u][cl]) continue;
if(cl == 0) {
for(auto V : g[u]) {
long long v = V.first;
long long c = V.second.first;
long long w = V.second.second;
if(d[v][c] > d[u][0]) {
d[v][c] = d[u][0];
pq.push(make_pair(-d[v][c],make_pair(v,c)));
}
if(d[v][0] > d[u][0] + min(sm[u][c]-w,w)) {
d[v][0] = d[u][0] + min(sm[u][c]-w,w);
pq.push(make_pair(-d[v][0],make_pair(v,0)));
}
}
}
else {
for(auto V : gc[u][cl]) {
long long v = V.first;
long long w = V.second;
long long c = cl;
if(d[v][0] > d[u][c] + sm[u][c] - w) {
d[v][0] = d[u][c] + sm[u][c] - w;
pq.push(make_pair(-d[v][0],make_pair(v,0)));
}
}
}
}
if(d[n][0] == 1000000000000000010) cout << -1 << endl;
else cout << d[n][0] << endl;
}
