#include <bits/stdc++.h>
using namespace std;
#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif
using ll = long long;
const ll inf = 1'000'000'000'000'000'000;
int n;
vector<vector<pair<int, ll>>> v;
vector<ll> dij(int start){
vector<ll> d(n, inf);
d[start] = 0;
set<pair<ll, int>> q;
for(int i = 0; i < n; i++){
q.insert({d[i], i});
}
while(!q.empty()){
auto [dd, u] = *q.begin();
q.erase(q.begin());
for(auto [i, j] : v[u]){
if(dd + j < d[i]){
q.erase({d[i], i});
d[i] = dd + j;
q.insert({d[i], i});
}
}
}
return d;
}
void add(int a, int b, int c){
v[a].emplace_back(b, c);
}
void solve(){
int m;
cin >> n >> m;
v.resize(n);
vector<map<int, vector<pair<int, int>>>> v1(n);
for(int i = 0; i < m; i++){
int a, b, c, p;
cin >> a >> b >> c >> p;
a--;b--;
v1[a][c].emplace_back(b, p);
v1[b][c].emplace_back(a, p);
}
for(int i = 0; i < n; i++){
for(auto [t, z] : v1[i]){
if(z.size() == 1){
add(i, z[0].first, 0);
}else{
for(auto j : z){
add(i, j.first, j.second);
}
}
}
}
auto d = dij(0);
if(d[n - 1] == inf){
cout << -1 << endl;
}else{
cout << d[n - 1] << endl;
}
}
signed main(){
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
