#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define endl '\n'
//data structures
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef pair<long long, long long> pll;
typedef pair<char, ll> ci;
typedef pair<string, ll> si;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<vector<ll>> vvi;
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define sz(a) ((ll)a.size())
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define fro front
#define pqueue priority_queue
#define ubound upper_bound
#define lbound lower_bound
#define beg(v) v.begin()
//bit operations
ll flip(ll x){
return ~(x) ^ (1 << 32);
}
ll allon(ll x){
return (1LL << x) - 1;
}
bool bit(ll a, ll i){
return (1LL << i) & a;
}
#define llpc(x) __builtin_popcountll(x)
#define ipc(x) __builtin_popcount(x)
#define iclz(x) __builtin_clz(x)
#define llclz(x) __builtin_clzll(x)
#define ictz(x) __builtin_ctz(x)
#define llctz(x) __builtin_ctzll(x)
//answers
#define cYES cout << "YES" << endl
#define cYes cout << "Yes" << endl
#define cyes cout << "yes" << endl
#define cNO cout << "NO" << endl
#define cNo cout << "No" << endl
#define cno cout << "no" << endl
#define ipsb cout << -1 << endl
const ll mod2 = 998244353;
const ll mod = 1000000007;
const ll inf = ll(1e18);
// read arr vec matr etc
#define fill(x, y) memset(x, y, sizeof(x))
void read(vector<ll> &x){
for(auto &e:x) cin >> e;
}
void sread(vector<string> &x){
for(auto &e:x) cin >> e;
}
void mread(vector<vector<ll>> &p, ll nnn, ll mmm){
for(ll i = 0; i < nnn; ++i){
vector<ll> pp;
for(ll j = 0; j < mmm; ++j){
ll wq; cin >> wq; pp.pb(wq);
}
p.pb(pp);
}
}
// Solution
void tc(){
int n, m; cin >> n >> m;
ll dp[m+1][2][2]; //edge idx, node, color matters y/n
for(int i = 0; i < m; ++i){
dp[i][0][0] = inf; dp[i][0][1] = inf; dp[i][1][0] = inf; dp[i][1][1] = inf;
}
vvi ed(n);
vvi edges;
for(int i = 0; i < m; ++i){
ll u, v, col, cost; cin >> u >> v >> col >> cost;
u--;
v--;
edges.pb({u, v, col, cost});
ed[u].pb(i);
ed[v].pb(i);
}
vector<map<int, ll>> x(n+1);
for(int i = 0; i < n; ++i){
for(auto e:ed[i]){
x[i][edges[e][2]] += edges[e][3];
}
}
pqueue<vi, vvi, greater<vi>> pq;
bool vis[m+1];
fill(vis, 0);
for(auto e:ed[0]){
ll totcost = x[0][edges[e][2]];
totcost -= edges[e][3];
ll othernode = 1;
if(edges[e][0] != 0){
othernode = 0;
}
pq.push({edges[e][3], e, othernode, 0});
pq.push({totcost, e, othernode, 1});
dp[e][othernode][0] = edges[e][3];
dp[e][othernode][1] = totcost;
}
while(sz(pq)){
vi state = pq.top();
pq.pop();
ll idx = state[1];
ll cost = state[0];
ll no = edges[idx][state[2]];
ll fat = state[3];
if(vis[idx] || dp[idx][state[2]][fat] != cost)continue;
vis[idx] = 1;
for(auto e:ed[no]){
if(e == idx)continue;
ll me = 0;
if(edges[e][0] == no){
me = 1;
}
ll totcost = x[no][edges[e][2]];
totcost -= edges[e][3];
if(fat == 0 && edges[idx][2] == edges[e][2]){
totcost -= edges[idx][3];
}
if(cost + edges[e][3] < dp[e][me][0]){
dp[e][me][0] = cost + edges[e][3];
pq.push({cost + edges[e][3], e, me, 0});
}
if(cost + totcost < dp[e][me][1]){
dp[e][me][1] = cost + totcost;
pq.push({cost + totcost, e, me, 1});
}
}
}
ll ans = inf;
for(auto e:ed[n-1]){
ll me = 0;
if(edges[e][0] != n-1){
me = 1;
}
ans = min(ans, min(dp[e][me][0], dp[e][me][1]));
}
if(ans == inf) ipsb;
else cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while(t--){
tc();
}
}
