#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
const ll INF=1e18+7;
vector<pair<int,pair<int,int>>>V[LIM];
ll odl[LIM], koszt[2*LIM], kolor[2*LIM];
map<pair<int,int>,int>odw;
map<pair<int,int>,ll>sum, ma1, ma2, ind1, ind2;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
rep(i, m) {
int a, b;
cin >> a >> b >> kolor[i] >> koszt[i]; --a; --b;
V[a].pb({kolor[i], {i, b}});
V[b].pb({kolor[i], {i, a}});
sum[{a, kolor[i]}]+=koszt[i];
sum[{b, kolor[i]}]+=koszt[i];
rep(j, 2) {
if(koszt[i]>=ma1[{a, kolor[i]}]) {
ma2[{a, kolor[i]}]=ma1[{a, kolor[i]}];
ind2[{a, kolor[i]}]=ind1[{a, kolor[i]}];
ma1[{a, kolor[i]}]=koszt[i];
ind1[{a, kolor[i]}]=i;
} else if(koszt[i]>=ma2[{a, kolor[i]}]) {
ma2[{a, kolor[i]}]=koszt[i];
ind2[{a, kolor[i]}]=i;
}
swap(a, b);
}
}
rep(i, n) {
odl[i]=INF;
sort(all(V[i]));
}
priority_queue<pair<ll,pair<int,int>>>q;
q.push({0, {0, -1}});
while(!q.empty()) {
ll o=-q.top().st, p=q.top().nd.st, lst=q.top().nd.nd; q.pop();
if(odw[{p, lst}]) continue;
odw[{p, lst}]=1;
if(odl[p]==INF) {
odl[p]=o;
for(auto i : V[p]) {
if(!odw[{i.nd.nd, i.nd.st}]) q.push({-o-koszt[i.nd.st], {i.nd.nd, i.nd.st}});
if(!odw[{i.nd.nd, -1}]) q.push({-o-sum[{p, i.st}]+koszt[i.nd.st], {i.nd.nd, -1}});
}
}
if(lst==-1) continue;
if(ind1[{p, kolor[lst]}]==lst) {
if(ma2[{p, kolor[lst]}]) {
pair<int,pair<int,int>>xd={kolor[lst], {ind2[{p, kolor[lst]}], -1}};
auto it=lower_bound(all(V[p]), xd);
int x=it-V[p].begin();
if(!odw[{V[p][x].nd.nd, -1}]) {
q.push({-o-sum[{p, kolor[lst]}]+koszt[lst], {V[p][x].nd.nd, -1}});
}
}
} else {
pair<int,pair<int,int>>xd={kolor[lst], {ind1[{p, kolor[lst]}], -1}};
auto it=lower_bound(all(V[p]), xd);
int x=it-V[p].begin();
if(!odw[{V[p][x].nd.nd, -1}]) {
q.push({-o-sum[{p, kolor[lst]}]+koszt[lst], {V[p][x].nd.nd, -1}});
}
}
}
cout << (odl[n-1]==INF?-1:odl[n-1]) << '\n';
}
