#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a){
return o << '(' << a.F << ',' << a.S << ')';
}
struct seg{
int tme, l, r, c;
bool operator<(seg b){
array<int, 4> ta = {tme, l, r, c};
array<int, 4> tb = {b.tme, b.l, b.r, b.c};
return ta < tb;
}
};
int n, m;
vector<seg> s;
bool solve(int msk){
set<pii> st;
st.insert(mp(1, n));
vector<seg> a;
for(int i = 0; i < m; i++){
if(1 << i & msk) a.eb(s[i]);
}
lsort(a);
int lst = 1;
for(auto i : a){
int sep = i.tme - lst;
lst = i.tme;
set<pii> tmp;
for(pii t : st){
int l = t.F, r = t.S;
l -= sep; r += sep;
l = max(l, 1);
r = min(r, n);
if(!tmp.empty() && tmp.rbegin()->S >= l - 1){
pii owo = *tmp.rbegin();
tmp.erase(prev(tmp.end()));
owo.S = r;
tmp.insert(owo);
}
else tmp.insert(mp(l, r));
}
st.swap(tmp);
tmp.clear();
int l = i.l, r = i.r;
for(pii t : st){
if(max(t.F, l) > min(t.S, r)){
tmp.insert(t);
continue;
}
int tl = t.F, tr = t.S;
if(l <= tl && tr <= r) continue;
else if(tr <= r) tmp.insert(mp(tl, l - 1));
else if(l <= tl) tmp.insert(mp(r + 1, tr));
else tmp.insert(mp(tl, l - 1)), tmp.insert(mp(r + 1, tr));
}
st.swap(tmp);
}
return st.empty();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
s.resize(m);
for(int i = 0; i < m; i++){
cin >> s[i].tme >> s[i].l >> s[i].r >> s[i].c;
}
ll ans = LLONG_MAX;
for(int i = 0; i < (1 << m); i++){
if(!solve(i)) continue;
//cerr << bitset<5>(i) << "\n";
ll sum = 0;
for(int j = 0; j < m; j++) if(1 << j & i) sum += s[j].c;
ans = min(ans, sum);
}
if(ans == LLONG_MAX) ans = -1;
cout << ans << "\n";
return 0;
}
