#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN 100100
map<int, pair<ll, vector<pair<int, int>>>> adj[MAXN];
int vis[MAXN];
map<int, vector<int>> visc[MAXN];
void add(int v, int u, int c, int p) {
auto pt=adj[v].find(c);
if(pt==adj[v].end()) {
adj[v][c]={0LL, vector<pair<int, int>>()};
pt=adj[v].find(c);
}
pt->second.first+=p;
pt->second.second.push_back({u, p});
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
while(m--) {
int a, b, c, p;
cin >> a >> b >> c >> p;
add(a, b, c, p);
add(b, a, c, p);
}
priority_queue<pair<pair<ll, int>, pair<int, int>>> pq;
pq.push({{0, 1}, {0, 0}});
while(!pq.empty()) {
auto pr=pq.top();
pq.pop();
ll d = -pr.first.first;
int v=pr.first.second;
int c=pr.second.first;
int src=pr.second.second;
if(!c) {
if(v==n) {
cout << d << endl;
return 0;
}
if(vis[v]) continue;
vis[v]=1;
for(auto pr : adj[v]) {
pq.push({{-d, v}, {pr.first, 0}});
}
for(auto pr1 : adj[v]) {
auto &vec=pr1.second.second;
for(auto pr2 : vec) {
pq.push({{-d, pr2.first}, {pr1.first, v}});
pq.push({{-(d+pr2.second), pr2.first}, {0, 0}});
}
}
} else {
auto p = visc[v].find(c);
if(p==visc[v].end()) {
visc[v][c]={};
p=visc[v].find(c);
}
auto &vec=p->second;
if(vec.size()<2) {
vec.push_back(src);
auto p2=adj[v].find(c);
auto &vec=p2->second.second;
for(auto pr: vec) {
if(pr.first==src) continue;
ll newd=d+p2->second.first-pr.second;
pq.push({{-newd, pr.first}, {0, 0}});
}
}
}
}
cout << -1 << endl;
return 0;
}
