/* Author: rrrr_wys
 **/

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
typedef double db;
typedef long long ll;
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;

const int N = 2000110;
const int P = 998244353;

int p[N], prime[N], tot, psize;
ll phi[N], mu[N];

ll cal(int n) {
  ll ans = 0;
  rep(g, 2, n) { ans += phi[n / g] * 2ll - (n / g) * 2ll; }
  return ans;
}
ll cal(int n, int m) {
  ll ans = 0;
  if (n < m)
    swap(n, m);
  rep(g, 2, m) {
    for (int dr, dl = 1; dl <= m / g; dl = dr + 1) {
      dr = min((m / g) / ((m / g) / dl), (n / g) / ((n / g) / dl));
      dr = min(dr, m / g);
      ans += (mu[dr] - mu[dl - 1]) * ((n / g) / dl) * ((m / g) / dl);
    }
    ans -= (n / g);
    ans -= (m / g);
    ans += 1;
  }
  return ans;
}

void prime_table() {
  int i, j, tot, t1;
  for (i = 1; i <= psize; i++)
    p[i] = i;
  phi[1] = 1;
  mu[1] = 1;
  for (i = 2, tot = 0; i <= psize; i++) {
    if (p[i] == i)
      prime[++tot] = i, phi[i] = i - 1, mu[i] = -1;
    for (j = 1; j <= tot && (t1 = prime[j] * i) <= psize; j++) {
      p[t1] = prime[j];
      if (i % prime[j] == 0) {
        phi[t1] = phi[i] * prime[j];
        break;
      }
      phi[t1] = phi[i] * (prime[j] - 1);
      mu[t1] = -mu[i];
    }
  }
  rep(i, 1, psize) phi[i] += phi[i - 1], mu[i] += mu[i - 1];
}

void init(int ps) {
  psize = ps;
  prime_table();
}
signed main() {
  int L, R;
  cin >> L >> R;
  init(N - 1);
  cout << cal(R, R) - cal(L - 1, R) - cal(R, L - 1) + cal(L - 1, L - 1) << "\n";
}
#include <iostream>
#include <vector>
#include <utility>
#include<algorithm>
#include <string>
#include <map>
#include <cmath>
#include <random>
#include <tuple>
#include <set>
#include <queue> 
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;


struct Edge {
    long long to;
    long long c;
  ll d;
};
using Graph = vector<vector<Edge>>;
using P = pair<long, int>;
const long long INF = 1LL << 60;

ll dijkstra(const Graph &G, vector<long long> &dis) {
    int N = G.size();
    dis.resize(N, INF);
    priority_queue<P, vector<P>, greater<P>> pq;
    dis[0] = 0;
    pq.emplace(dis[0], 0);
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if (dis[v] < p.first) {
            continue;
        }
        for (auto &e : G[v]) {
          ll cost;
          ll d = e.d;
          ll cc = e.c;
          if(dis[v] > sqrt(d)-1){
            cost = cc +(d)/(dis[v]+1) + dis[v];
          }else{
            cost = sqrt(d) + (d)/(sqrt(d)+1);
            if(d/(sqrt(d)) + sqrt(d)-1 < cost){
              cost = d/(sqrt(d)) + sqrt(d)-1;
            }
            cost += cc;
          }
            if (dis[e.to] > cost) {
                dis[e.to] = cost;
                pq.emplace(dis[e.to], e.to);
            }
        }
    }
  if(dis[N-1] == INF){
    dis[N-1] = -1;
  }
  return dis[N-1];
}


int main(){
  
  ll n,m;
  cin >> n >> m;
  Graph G(n);
  rep(i,m){
    ll b,c,d,e;
    cin >> b >> c >> d >> e;
    G[b-1].push_back({c-1,d,e});
    G[c-1].push_back({b-1,d,e});
  }
  vector<ll> dis(n,INF);
  cout << dijkstra(G,dis) << endl;
  
  
  return 0;
}