#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;
map<int, vii> g[MAXN];
set<pair<ll, ii>> s;
map<int, ll> dis[MAXN], su[MAXN];
void upd(int x, int col, ll nd){
if(dis[x][col] <= nd) return;
s.erase({dis[x][col], {x, col}});
dis[x][col] = nd;
s.insert({dis[x][col], {x, col}});
}
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});
su[a][c] += p;
su[b][c] += p;
}
for(int i=1; i<=n; i++){
for(auto &x : g[i]){
dis[i][x.X] = INF;
s.insert({(ll)dis[i][x.X], {i, x.X}});
}
if(i == 1) dis[i][0] = 0;
else dis[i][0] = INF;
s.insert({(ll)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 << d << "\n";
return;
}
if(col == 0){
for(auto &x : g[u]){
for(auto &y : x.Y){
int v = y.X, b = x.X;
ll tez = y.Y;
tez = min(tez, su[u][b] - tez);
ll nd = d + (ll)tez;
upd(v, 0, nd);
upd(v, b, d);
}
}
}else{
if(g[u][col].size() == 1) continue;
for(auto &x : g[u][col]){
ll tez = su[u][col] - (ll)x.Y;
int v = x.X;
ll nd = d + (ll)tez;
upd(v, 0, nd);
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> tt;
while(tt--) solve();
return 0;
}
