#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int n, m, c[200200], p[200200];
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; cin >> x >> y >> c[i] >> p[i];
s[x][c[i]] += p[i], s[y][c[i]] += p[i], d[x][i] = d[y][i] = {INF, INF};
v1[x][c[i]].push_back({y, i}), v1[y][c[i]].push_back({x, i});
v2[x][c[i]].push_back({y, i}), v2[y][c[i]].push_back({x, i});
}
pq.push({0, 1, -1, 0});
while(!pq.empty()) {
auto [cost, u, id, type] = pq.top(); pq.pop();
if(d[u][id][type] < cost) continue;
if(u == n) return cout << cost, 0;
for(auto [xcol, v] : v1[u]) {
ll S = s[u][xcol];
for(auto [x, y] : v) {
ll C1 = cost + S - p[y], C2 = cost + p[y];
if((!type || c[id] != xcol) && C1 < d[x][y][1]) d[x][y][1] = C1, pq.push({C1, x, y, 1});
if(C2 < d[x][y][0]) d[x][y][0] = C2, pq.push({C2, x, y, 0});
}
}
// 변경된 색으로 들어와서 변경되기 전 색과 같은 간선의 색을 그대로 나가는 처리
if(type == 1) continue;
auto &v = v2[u][c[id]];
ll S = s[u][c[id]];
for(auto [x, y] : v) if(y != id) {
ll C = cost + S - p[y] - p[id];
if(C < d[x][y][1]) d[x][y][1] = C, pq.push({C, x, y, 1});
}
v2[u].erase(c[id]);
}
cout << -1;
}
