#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 1e5;
const int M = 2e5;
const ll INF = 1e18;
int n,m;
struct edge{
int u,v,c,d;
}a[M+5];
struct edg1{
int v,c,d;
bool operator < (const edg1&other) const{
return v < other.v;
}
};
vector<edg1> g[N+5];
vector<pair<int,ll>> G[N+5];
ll dist[N+5];
int cost[M+5],cnt[M+5],lst[M+5];
void dji(int x){
for(int i = 1 ; i <= n ; ++i) dist[i] = INF;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
dist[x] = 0;
pq.push({0,x});
while(!pq.empty()){
pair<ll,int> t = pq.top();
pq.pop();
ll w = t.fi;
int u = t.se;
// cout << u << ' ' << w << "!\n";
if(dist[u] > w) continue;
for(pair<int,ll> i : G[u]) if(w + i.se < dist[i.fi]){
dist[i.fi] = w + i.se;
pq.push({dist[i.fi],i.fi});
}
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1 ; i <= m ; ++i){
cin >> a[i].u >> a[i].v >> a[i].c >> a[i].d;
g[a[i].u].push_back({a[i].v,a[i].c,a[i].d});
g[a[i].v].push_back({a[i].u,a[i].c,a[i].d});
}
for(int i = 1 ; i <= n ; ++i){
// cout << i << ":\n";
for(edg1 j : g[i]){
cnt[j.c]++;
}
for(edg1 j : g[i]){
//cout << cnt[j.c] << ',' << j.v << '\n';
if(cnt[j.c] == 1) {
// cout << i << ',' << j.v << ',' << 0 << '\n';
G[i].push_back({j.v,0});
//G[j.v].push_back({i,0});
}
if(cnt[j.c] == 2) lst[j.c] = j.v,cost[j.c] = j.d;
//if(cnt[j.c] >= 3) {
// cout << i << ',' << j.v << ',' << j.d << '\n';
//G[j.v].push_back({i,a[i].d});
//}
if(cnt[j.c] >= 2){
cost[j.c] += j.d;
}
}
for(edg1 j : g[i]){
if(cnt[j.c] == 2 && j.v != lst[j.c]) {
// cout << j.v << ',' << lst[j.c] << '.' << min(cost[j.c],j.d) << '\n';
G[j.v].push_back({lst[j.c],min(cost[j.c],j.d)});
G[lst[j.c]].push_back({j.v,min(cost[j.c],j.d)});
}
if(cnt[j.c] >= 2){
G[i].push_back({j.v,min(j.d,cost[j.c]-j.d)});
}
}
for(edg1 j : g[i]){
cnt[j.c]--;
lst[j.c] = cost[j.c] = 0;
}
}
dji(1);
if(dist[n] >= INF) cout << -1 << '\n';
else cout << dist[n];
return 0;
}
