#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;
const int mxN = 100001;
int N, M;
struct Treatment {
int T, L, R, C;
};
vector<Treatment> treat;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
FOR(i,1,M){
int T, L, R, C;
cin >> T >> L >> R >> C;
treat.push_back({T,L,R,C});
}
sort(ALL(treat),[](Treatment &a, Treatment &b){ return a.T < b.T; });
ll ans = 1e18;
FOR(b,0,(1<<M)-1){
set<ii> ranges, tmp;
ranges.insert(ii(1,N));
int t = 1;
ll cost = 0;
FOR(i,0,M-1) if (b&(1<<i)) {
auto tr = treat[i];
cost += tr.C;
if (t < tr.T) {
int e = tr.T - t;
t = tr.T;
tmp.clear();
for (auto it = ranges.begin(), y = it; it != ranges.end(); ++it) {
auto x = *it;
x.first = max(1,x.first-e);
x.second = min(N,x.second+e);
while ((y = next(it)) != ranges.end()) {
if (x.second >= y->first-e) {
x.second = min(N,y->second+e);
ranges.erase(y);
} else break;
}
tmp.insert(x);
}
ranges = tmp;
}
tmp.clear();
for (auto& x : ranges) {
if (x.second < tr.L || x.first > tr.R) tmp.insert(x);
else {
if (x.first < tr.L) tmp.insert(ii(x.first,tr.L-1));
if (x.second > tr.R) tmp.insert(ii(tr.R+1,x.second));
}
}
ranges = tmp;
}
if (ranges.empty()) {
//TRACE(b _ cost);
ans = min(ans,cost);
}
}
if (ans == 1e18) cout << -1 << '\n';
else cout << ans << '\n';
}
