#include <bits/stdc++.h>
#define int long long
#define inf 1ll<<62
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define pii pair<int, int>
#define C first
#define nb second.first
#define sum second.first
#define yen second.second
#define sp <<' '<<
using namespace std;
signed main(){
fastio
int n, m, a, b, c, p;
cin >> n >> m;
bitset<100001> vst;
vector<vector<pair<int, pii>>> e(n+1); //color, neighbor, cost
vector<vector<pair<int, pii>>> s(n+1, vector<pair<int, pii>> (1, {0ll, {0ll, inf}}));
auto it=s[0].begin();
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0ll, 1ll});
// color, sum of cost, needed cost
for(; m; m--){
cin >> a >> b >> c >> p;
e[a].push_back({c, {b, p}});
e[b].push_back({c, {a, p}});
}
for(int i=1; i<=n; i++){
if(e[i].empty()) continue;
sort(e[i].begin(), e[i].end());
c = 0;
for(const auto &x: e[i]){
if(x.C!=c){
c = x.C;
s[i].push_back({c, {0ll, inf}});
}
s[i].back().sum += x.yen;
}
}
/*for(int i=1; i<=n; i++){
cout << i << ":\n";
for(const auto &x: e[i])
cout << x.C sp x.nb sp x.yen << '\n';
}
for(int i=1; i<=n; i++){
cout << i << ":\n";
for(const auto &x: s[i])
cout << x.C sp x.sum sp x.yen << '\n';
}*/
s[1][0].yen = 0;
while(!pq.empty()){
m = pq.top().second;
pq.pop();
if(m==n) break;
if(vst[m]) continue;
vst[m] = 1;
c = 0; //index of s
for(const auto &x: e[m]){
if(x.C!=s[m][c].C) c++;
if(vst[x.nb]) continue;
p = min(s[m][0].yen+min(x.yen, s[m][c].sum-x.yen), s[m][c].yen-x.yen);
//cout << m sp x.nb sp p;
if(p<s[x.nb][0].yen){
s[x.nb][0].yen = p;
pq.push({p, x.nb});
}
it = lower_bound(s[x.nb].begin(), s[x.nb].end(), make_pair(s[m][c].C, make_pair(0ll, 0ll)));
it->yen = min(s[m][0].yen+(it->sum), it->yen);
//cout sp (it->C) sp (it->yen) sp (it->sum) << '\n';
}
}
if(s[n][0].yen==inf) cout << "-1\n";
else cout << s[n][0].yen << '\n';
return 0;
}
