#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define vll vector<ll>
#define G vector<vll >
#define gg vector<int>
#define F first
#define S second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define RFOR(i,a,b) for(int i=a;i>=b;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define endl '\n'
#define clr(a) memset(a,0,sizeof(a))
#define all(x) x.begin(),x.end()
#define rll read_ll();
#define gc getchar
#define pc putchar
typedef long long ll;
template<class T> inline T lcm(T a,T b){
return a/gcd(a,b)*b;
}
template<typename T>
void debug(T first) {
cout << first << "\n";
}
template<typename T, typename... Args>
void debug(T first, Args... args) {
cout << first << " ";
debug(args...);
}
ll read_ll(){char c=gc();while((c<'0'||c>'9')&&c!='-')c=gc();ll ret=0;int neg=0;if(c=='-')neg=1,c=gc();while(c>='0'&&c<='9'){ret=10*ret+c-48;c=gc();}return neg?-ret:ret;}
struct node {
ll u,start, end,eno;
node(ll uu, ll st, ll en, ll no):u(uu), start(st), end(en), eno(no){}
};
const ll INF = 1e18;
class graph {
public :
ll n,e,s,t,cnt;
// priority_queue<ll,vector<ll>,less<ll>>p;
priority_queue<pair<ll,pair<ll,ll> >,vector<pair<ll,pair<ll,ll> > >,greater<pair<ll,pair<ll,ll> > > > pq;
vector<vector<node> >adj;
vector<ll>dist;
vector<bool>visited;
graph(int nodes, int edges) {
n = nodes, e = edges;
adj.resize(n+1);
dist.resize(n+1);
visited.resize(e+1);
fill(all(visited),false);
fill(all(dist),INF);
s = 1, t = n;
cnt = 0;
}
void addEdge(int u, int v, int start, int end) {
adj[u].pb(node(v,start,end,cnt++));
}
void bfs() {
pq.push({0,{0,1}});
while(!pq.empty()) {
auto current = pq.top(); pq.pop();
ll f = current.F;
ll currentTime = current.S.F;
ll u = current.S.S;
if(u == n) break;
// if you add visited, answer will not be minium since cycles wont be allowed
for(auto node : adj[u]) {
ll v = node.u, start = node.start, end = node.end;
ll eno = node.eno;
if(currentTime > start) continue;
ll currentFrustration = f + (currentTime-start)*(currentTime-start);
if(dist[v] > currentFrustration) {
dist[v] = currentFrustration;
}
// debug("visit",u,"->",v,":",eno,dist[v]);
pq.push({currentFrustration,{end,v}});
}
}
}
};
int main()
{
int n, e; cin>>n>>e;
graph g(n,e);
for(int i = 0; i < e; i++) {
int u, v, st, en;
cin>>u>>v>>st>>en;
g.addEdge(u, v, st, en);
}
g.bfs();
cout<<g.dist[n]<<endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1cCB1cHBlcl9ib3VuZAojZGVmaW5lIHZsbCB2ZWN0b3I8bGw+CiNkZWZpbmUgRyB2ZWN0b3I8dmxsID4KI2RlZmluZSBnZyB2ZWN0b3I8aW50PgojZGVmaW5lIEYgZmlyc3QKI2RlZmluZSBTIHNlY29uZAojZGVmaW5lIHBsbCBwYWlyPGxsLGxsPgojZGVmaW5lIHBpaSBwYWlyPGludCxpbnQ+CiNkZWZpbmUgUkZPUihpLGEsYikgZm9yKGludCBpPWE7aT49YjtpLS0pCiNkZWZpbmUgRk9SKGksYSxiKSBmb3IoaW50IGk9YTtpPD1iO2krKykKI2RlZmluZSBlbmRsICdcbicKI2RlZmluZSBjbHIoYSkgbWVtc2V0KGEsMCxzaXplb2YoYSkpCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSx4LmVuZCgpCiNkZWZpbmUgcmxsIHJlYWRfbGwoKTsKI2RlZmluZSBnYyBnZXRjaGFyCiNkZWZpbmUgcGMgcHV0Y2hhcgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdGVtcGxhdGU8Y2xhc3MgVD4gaW5saW5lIFQgbGNtKFQgYSxUIGIpewogICAgICAgIHJldHVybiBhL2djZChhLGIpKmI7Cn0KdGVtcGxhdGU8dHlwZW5hbWUgVD4Kdm9pZCBkZWJ1ZyhUIGZpcnN0KSB7CiAgICBjb3V0IDw8IGZpcnN0IDw8ICJcbiI7Cn0KdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUuLi4gQXJncz4Kdm9pZCBkZWJ1ZyhUIGZpcnN0LCBBcmdzLi4uIGFyZ3MpIHsKICAgIGNvdXQgPDwgZmlyc3QgPDwgIiAiOwogICAgZGVidWcoYXJncy4uLik7Cn0KCgpsbCByZWFkX2xsKCl7Y2hhciBjPWdjKCk7d2hpbGUoKGM8JzAnfHxjPic5JykmJmMhPSctJyljPWdjKCk7bGwgcmV0PTA7aW50IG5lZz0wO2lmKGM9PSctJyluZWc9MSxjPWdjKCk7d2hpbGUoYz49JzAnJiZjPD0nOScpe3JldD0xMCpyZXQrYy00ODtjPWdjKCk7fXJldHVybiBuZWc/LXJldDpyZXQ7fQoKc3RydWN0IG5vZGUgewoJbGwgdSxzdGFydCwgZW5kLGVubzsKCW5vZGUobGwgdXUsIGxsIHN0LCBsbCBlbiwgbGwgbm8pOnUodXUpLCBzdGFydChzdCksIGVuZChlbiksIGVubyhubyl7fQp9OwoKY29uc3QgbGwgSU5GID0gMWUxODsKY2xhc3MgZ3JhcGggewoJcHVibGljIDogCgkJbGwgbixlLHMsdCxjbnQ7CgkJLy8gcHJpb3JpdHlfcXVldWU8bGwsdmVjdG9yPGxsPixsZXNzPGxsPj5wOwoJCXByaW9yaXR5X3F1ZXVlPHBhaXI8bGwscGFpcjxsbCxsbD4gPix2ZWN0b3I8cGFpcjxsbCxwYWlyPGxsLGxsPiA+ID4sZ3JlYXRlcjxwYWlyPGxsLHBhaXI8bGwsbGw+ID4gPiA+IHBxOwoJCXZlY3Rvcjx2ZWN0b3I8bm9kZT4gPmFkajsKCQl2ZWN0b3I8bGw+ZGlzdDsKCQl2ZWN0b3I8Ym9vbD52aXNpdGVkOwoJCWdyYXBoKGludCBub2RlcywgaW50IGVkZ2VzKSB7CgkJCW4gPSBub2RlcywgZSA9IGVkZ2VzOwoJCQlhZGoucmVzaXplKG4rMSk7CgkJCWRpc3QucmVzaXplKG4rMSk7CgkJCXZpc2l0ZWQucmVzaXplKGUrMSk7CgkJCWZpbGwoYWxsKHZpc2l0ZWQpLGZhbHNlKTsKCQkJZmlsbChhbGwoZGlzdCksSU5GKTsKCQkJcyA9IDEsIHQgPSBuOwoJCQljbnQgPSAwOwoJCX0KCQl2b2lkIGFkZEVkZ2UoaW50IHUsIGludCB2LCBpbnQgc3RhcnQsIGludCBlbmQpIHsKCQkJYWRqW3VdLnBiKG5vZGUodixzdGFydCxlbmQsY250KyspKTsKCQl9CgkJdm9pZCBiZnMoKSB7CgkJCXBxLnB1c2goezAsezAsMX19KTsKCQkJd2hpbGUoIXBxLmVtcHR5KCkpIHsKCQkJCWF1dG8gY3VycmVudCA9IHBxLnRvcCgpOyBwcS5wb3AoKTsKCQkJCWxsIGYgPSBjdXJyZW50LkY7CgkJCQlsbCBjdXJyZW50VGltZSA9IGN1cnJlbnQuUy5GOwoJCQkJbGwgdSA9IGN1cnJlbnQuUy5TOwoJCQkJaWYodSA9PSBuKSBicmVhazsKCQkJCS8vIGlmIHlvdSBhZGQgdmlzaXRlZCwgYW5zd2VyIHdpbGwgbm90IGJlIG1pbml1bSBzaW5jZSBjeWNsZXMgd29udCBiZSBhbGxvd2VkCgkJCQlmb3IoYXV0byBub2RlIDogYWRqW3VdKSB7CgkJCQkJbGwgdiA9IG5vZGUudSwgc3RhcnQgPSBub2RlLnN0YXJ0LCBlbmQgPSBub2RlLmVuZDsKCQkJCQlsbCBlbm8gPSBub2RlLmVubzsKCQkJCQkKCQkJCQkKCQkJCQlpZihjdXJyZW50VGltZSA+IHN0YXJ0KSBjb250aW51ZTsKCQkJCQlsbCBjdXJyZW50RnJ1c3RyYXRpb24gPSBmICsgKGN1cnJlbnRUaW1lLXN0YXJ0KSooY3VycmVudFRpbWUtc3RhcnQpOwoJCQkJCWlmKGRpc3Rbdl0gPiBjdXJyZW50RnJ1c3RyYXRpb24pIHsKCQkJCQkJZGlzdFt2XSA9IGN1cnJlbnRGcnVzdHJhdGlvbjsKCQkJCQl9CgkJCQkJLy8gZGVidWcoInZpc2l0Iix1LCItPiIsdiwiOiIsZW5vLGRpc3Rbdl0pOwoJCQkJCXBxLnB1c2goe2N1cnJlbnRGcnVzdHJhdGlvbix7ZW5kLHZ9fSk7CgkJCQl9CgkJCX0KCQl9Cn07CgppbnQgbWFpbigpCnsKCWludCBuLCBlOyBjaW4+Pm4+PmU7CglncmFwaCBnKG4sZSk7Cglmb3IoaW50IGkgPSAwOyBpIDwgZTsgaSsrKSB7CgkJaW50IHUsIHYsIHN0LCBlbjsKCQljaW4+PnU+PnY+PnN0Pj5lbjsKCQlnLmFkZEVkZ2UodSwgdiwgc3QsIGVuKTsKCX0KCWcuYmZzKCk7Cgljb3V0PDxnLmRpc3Rbbl08PGVuZGw7CglyZXR1cm4gMDsKfQ==