#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int MOD2 = 998'244'353;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

template<class T, class S> inline bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S> inline bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}

template<class T, class S> inline bool exist(std::set<T> &s, const S &e){
    return (s.find(e) != s.end());
}








struct edge{
    int to;
    long long C, D;
    edge(int To, long long c, long long d): to(To), C(c), D(d){}
};




void dijkstra(int s, std::vector<std::vector<edge>> &G, std::vector<long long> &d, std::vector<int> &prv){
    //pair<int, int> first: 距離　second: 頂点
    std::priority_queue<std::pair<long long, int>,
                        std::vector<std::pair<long long, int>>,
                        std::greater<std::pair<long long, int>>> que;
    int V{int(G.size())};
    d.resize(V, LINF+3);
    prv.resize(V, NIL);
    d[s] = 0;
    que.emplace(0, s);

    while(!que.empty()){
        std::pair<long long, int> p{que.top()}; que.pop();
        int v{p.second};
        if(d[v] < p.first) continue;
        for(edge &e: G[v]){
            long long TT{(long long)(std::sqrt((long double)(e.D)) - 1)};
            long long mn{LINF+8};
            for(int i{-300}; i <= 300; ++i){
                long long t{TT + i};
                if(t < d[v]) t = d[v];
                chmin(mn, t + e.C + e.D/(t + 1));
            }
            if(d[e.to] > mn){
                d[e.to] = mn;
                prv[e.to] = v;
                que.emplace(d[e.to], e.to);
            }
        }
    }
}

int main(){
    int N, M; std::cin >> N >> M;
    std::vector<std::vector<edge>> G(N);
    {
        int A, B; long long C, D;
        for(int i{0}; i < M; ++i){
            std::cin >> A >> B >> C >> D;
            G[A-1].emplace_back(B-1, C, D);
            G[B-1].emplace_back(A-1, C, D);
        }
    }
    std::vector<long long> d;
    std::vector<int> p;
    dijkstra(0, G, d, p);
    std::cout << (d[N-1] <= LINF ? d[N-1]: -1LL) << std::endl;
    return 0;
}

#include <bits/stdc++.h>
typedef long long int   LL;
typedef long double     LD;
#define nl              '\n'
#define ff              first
#define ss              second
#define inf             INT_MAX
#define SQR(a)          (a) * (a)
#define pb              push_back
#define GCD(a, b)       __gcd(a, b)
#define PI              2.0*acos(0.0)
#define pii             pair<int,int>
#define pll             pair<long long,long long>
#define LCM(a, b)       (a * b) / GCD(a, b)
#define mem(a,b)        memset(a,b,sizeof(a))
#define srtv(v)         sort(v.begin(),v.end())
#define Rep(i,a,b)      for(int i = a; i <= b; i++)
#define rep(i,a,b)      for(int i = a; i >= b; i--)
#define FOR(i,a)        for(int i=0;i<a;i++)
//#pragma                 GCC optimize("Ofast,no-stack-protector")
//#pragma                 GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma                 GCC optimize("unroll-loops")
#define boost           ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inout           freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)

#define si(x)           scanf("%d",&x)
#define pi(x)           printf("%d",x)
#define sss(str)         scanf("%s",str)
#define pl(x)           printf("%lld",x)
#define sl(x)           scanf("%lld",&x)
#define sii(x,y)        scanf("%d %d",&x,&y)
#define sll(x,y)        scanf("%lld %lld",&x,&y)
#define siii(x,y,z)     scanf("%d %d %d",&x,&y,&z)
#define slll(x,y,z)     scanf("%lld %lld %lld",&x,&y,&z)
using namespace std;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};


//--------------------------code starts here---------------------------------------
const int maxn=2e5+5;

vector<LL> adj[maxn];
set<LL> st;
vector<pll> v;
int n;

LL dp[maxn][2];

LL calc(LL x,LL y)
{
    /*if(x<0 && y<0)
    {
        return abs(fabs(x)-fabs(y));
    }

    if(x<0 && y>=0)
    {
        return fabs(x)+y;
    }
    if(x>0 && y>0)
        return abs(y-x);*/
    
    return abs(x-y);
}
LL lowest=100000000000000;
LL fun(int pos,int flag)
{
    if(pos==n)
    {
        if(flag==0)
        {
            return abs(lowest-v[pos-1].ff);
        }
        else
        {
            return abs(lowest-v[pos-1].ss);
        }
    }

    if(dp[pos][flag]!=-1)
        return dp[pos][flag];

    LL res=10000000000000000;
    if(flag==0)
    {
        LL dist=calc(v[pos-1].ff,v[pos].ff);
        dist+=calc(v[pos].ff,v[pos].ss);
        res=min(res,dist+fun(pos+1,1));

        dist=calc(v[pos-1].ff,v[pos].ss);
        dist+=calc(v[pos].ff,v[pos].ss);
        res=min(res,dist+fun(pos+1,0));
    }
    else
    {
        LL dist=calc(v[pos-1].ss,v[pos].ff);
        dist+=calc(v[pos].ff,v[pos].ss);
        res=min(res,dist+fun(pos+1,1));

        dist=calc(v[pos-1].ss,v[pos].ss);
        dist+=calc(v[pos].ff,v[pos].ss);
        res=min(res,dist+fun(pos+1,0));
    }

    return dp[pos][flag]=res;
}

void solve(int test)
{
    si(n);
    FOR(i,n)
    {
        LL x,y;
        sll(x,y);
        adj[y].pb(x);
        st.insert(y);
    }

    v.pb({0,0});

    for(auto i:st)
    {
        sort(adj[i].begin(),adj[i].end());
        LL frst=adj[i][0];
        LL lst=adj[i][adj[i].size()-1];
        v.pb({frst,lst});

        lowest=min(lowest,frst);
        lowest=min(lowest,lst);
    }

    for(int i=0;i<v.size();i++)
    {
        v[i].ff+=lowest;
        v[i].ss+=lowest;
    }

    n=v.size();

    mem(dp,-1);
    LL res=fun(1,0);
    printf("%lld\n",res);

}

int main()
{
	int test=1;
    //si(test);
    Rep(i,1,test)
    {
        solve(test);
    }

	return 0;
}
