#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int n, m;
map<int, vector<array<int, 2>>> v1[100100], v2[100100];
map<int, ll> s[100100];
map<int, array<ll, 2>> d[100100];
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=m;i++) {
int x, y, c, p; cin >> x >> y >> c >> p;
s[x][c] += p, s[y][c] += p, d[x][c] = d[y][c] = {INF, INF};
v1[x][c].push_back({y, p}), v1[y][c].push_back({x, p});
v2[x][c].push_back({y, p}), v2[y][c].push_back({x, p});
}
pq.push({0, 1, -1, 0});
while(!pq.empty()) {
auto [c, u, col, type] = pq.top(); pq.pop();
if(d[u][col][type] < c) continue;
if(u == n) return cout << c, 0;
auto it = v1[u].begin();
while(it != v1[u].end()) {
if(type && it->first == col) { it++; continue; }
auto &[xcol, v] = *it;
ll p = s[u][xcol];
for(auto [x, y] : v) {
ll C1 = c + y, C2 = c + p - y;
if(C1 < d[x][xcol][1]) d[x][xcol][1] = C1, pq.push({C1, x, xcol, 1});
if(C2 < d[x][xcol][0]) d[x][xcol][0] = C2, pq.push({C2, x, xcol, 0});
}
it = v1[u].erase(it);
}
if(type == 1) continue;
// 변경된 색으로 들어와서 변경되기 전 색과 같은 간선의 색을 다시 변경해서 나가는 처리
auto &v = v2[u][col];
ll p = s[u][col];
if(v.size() > 1) for(auto [x, y] : v) {
ll C = c+p-y-1;
if(C < d[x][col][0]) d[x][col][0] = C, pq.push({C, x, col, 0});
}
v2[u].erase(col);
}
cout << -1;
}
