#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int MAXN = 1e5 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int off = 1 << logo;
map<int, vii> g[MAXN];
vii adj[MAXN];
set<pair<ll, ii>> s;
map<int, ll> dis[MAXN];
void solve(){
int n, m;
cin >> n >> m;
for(int i=0; i<m; i++){
int a, b, c, p;
cin >> a >> b >> c >> p;
g[a][c].PB({b, p});
g[b][c].PB({a, p});
}
for(int i=1; i<=n; i++){
for(auto &x : g[i]){
dis[i][x.X] = INF;
s.insert({dis[i][x.X], {i, x.X}});
}
if(i == 1) dis[i][0] = 0;
else dis[i][0] = INF;
s.insert({dis[i][0], {i, 0}});
}
while(!s.empty()){
pair<ll, ii> cr = *s.begin();
s.erase(s.begin());
int u = cr.Y.X, col = cr.Y.Y;
ll d = cr.X;
if(u == n and col == 0){
if(cr.X >= INF) cout << -1 << "\n";
else cout << cr.X << "\n";
return;
}
if(col == 0){
for(auto &x : g[u]){
for(auto &y : x.Y){
int v = y.X, tez = y.Y, b = x.X;
if(x.Y.size() == 1) tez = 0;
ll nd = d + tez;
if(nd < dis[v][0]){
s.erase({dis[v][0], {v, 0}});
dis[v][0] = nd;
s.insert({dis[v][0], {v, 0}});
}
nd = d;
if(nd < dis[v][b]){
s.erase({dis[v][b], {v, b}});
dis[v][b] = nd;
s.insert({dis[v][b], {v, b}});
}
}
}
}else{
ll csu = 0;
for(auto &x : g[u][col]) csu += x.Y;
for(auto &x : g[u][col]){
ll tez = csu - x.Y;
int v = x.X;
ll nd = tez + d;
if(nd < dis[v][0]){
s.erase({dis[v][0], {v, 0}});
dis[v][0] = nd;
s.insert({dis[v][0], {v, 0}});
}
if(nd < dis[v][col]){
s.erase({dis[v][col], {v, col}});
dis[v][col] = nd;
s.insert({dis[v][col], {v, col}});
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> tt;
while(tt--) solve();
return 0;
}
