#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<map<int,vector<pair<int,int>>>> adj(n);
for (int i=0,u,v,c,w;i<m;i++) {
cin >> u >> v >> c >> w;
--u,--v;
adj[u][c].emplace_back(v,w);
adj[v][c].emplace_back(u,w);
}
const ll inf = 1e18;
vector<ll> dist(n,inf);
dist[0] = 0;
set<pair<ll,int>> q;
q.emplace(0,0);
while(!q.empty()) {
int x=(*q.begin()).second;q.erase(q.begin());
for (auto &edges: adj[x]) {
if (edges.second.size()==1) {
for (auto &[y,w]: edges.second) {
ll p=dist[y];
if (cmin(dist[y],dist[x])) {
q.erase(make_pair(p,y));
q.emplace(dist[y],y);
}
}
continue;
}
multiset<ll> dists;
ll sum=0;
for (auto &[y,w]: edges.second) {
dists.insert(dist[y]);
sum+=w;
}
for (auto &[y,w]: edges.second) {
dists.erase(dists.find(dist[y]));
ll d=min({dist[x]+w,
*dists.begin()+sum-w,
dist[x]+sum-w});
ll p=dist[y];
if (cmin(dist[y],d)) {
q.erase(make_pair(p,y));
q.emplace(d,y);
}
dists.insert(dist[y]);
}
}
}
cout << (dist[n-1]==inf?-1:dist[n-1]) << endl;
}
