#include <iostream>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define V vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F first
#define S second
#define sqr(x) (x)*(x)
#define mp make_pair
#define mtp make_tuple
#define tpii tuple<int,int,int>
#define ckmax(a,b) a=max(a,b)
#define ckmin(a,b) a=min(a,b)
#define rep(n) for(int i=0;i<n;i++)
#define inf INT_MAX
#define debug(x) cerr<<x<<'\n';
#define quick ios_base::sync_with_stdio(0),cin.tie(0);long double nownow=clock();
#define total_time cerr<<(clock()-nownow)/CLOCKS_PER_SEC*1000<<" (ms)\n";
using namespace std;
template<typename T>void in(vector<T> &a){for(auto &i:a)cin>>i;}
template<typename T>void in(vector<T> &a,int n){for(auto i=0;i<n;i++)cin>>a[i];}
template<typename T>void out(vector<T> &a){for(auto &i:a)cout<<i;cout<<'\n';}
#define int long long
#define input freopen("/Users/wangkaiyu/Downloads/Q_6_24_3.in","r",stdin);

signed main(){
    quick
    int n,m;
    cin>>n>>m;
    vvi a(n+1);
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        a[x].pb(y);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        queue<int> q;
        q.push(i);
        vi f(n+1,0);
        f[i]=1;
        while(!q.empty()){
            cnt++;
            int t=q.front();
            for(int j:a[t]){
                if(f[j]==0)
                    q.push(j);
                f[j]=1;
            }
            q.pop();
        }
    }cout<<cnt<<'\n';
    total_time
    return 0;
}

#pragma GCC optimize("O3")
//#pragma GCC target("avx")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <iomanip>
#include <list>
#include <stack>
using namespace std;
#define re return
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all(x)),x.resize(unique(all(x))-x.begin())
#define fi first
#define se second
#define ss second.second
#define sf second.first
#define ff first.first
#define fs first.second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define PI 3.14159265358979323846
#define E 2.71828182845904523536
#define er erase
#define in insert
#define fo(i,n) for((i)=0;(i)<(n);(i)++)
#define ro(i,n) for((i)=n-1;(i)>=0;(i)--)
#define fr(i,j,n) for((i)=(j);(i)<(n);(i)++)
#define rf(i,j,n) for((i)=((n)-1);(i)>=(j);(i)--)
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
void eras(map<int,int> &m,int x)
{
    m[x]--;
    if (!m[x]) m.erase(x);
}
ostream& operator <<(ostream &out,__int128 x)
{
    out<<(ll)x;
    re out;
}
istream& operator >>(istream &in,__int128 &x)
{
    ll temp;
    in>>temp;
    x=temp;
    re in;
}
const int N=(int)3e5+100;
const int M=(int)1e7+10;
const ll inf=(ll)1e18+100;
const double eps=1e-9;
#define filename ""
    int n;
    vector<pair<int,pair<int,int> > > v[N];
    ll d[N];
bool sss(int x,int y)
{
    if (d[x]==d[y]) re x<y;
    re d[x]<d[y];
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //freopen(filename".in","r",stdin);
    //freopen(filename".out","w",stdout);
    //freopen("ans.txt","w",stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int m;
    cin>>n>>m;
    int i;
    fo(i,m)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a--;
        b--;
        v[a].pb({b,{c,d}});
        v[b].pb({a,{c,d}});
    }
    set<int,bool(*)(int,int)> s(sss);
    fr(i,1,n)
    {
        d[i]=inf;
        s.in(i);
    }
    s.in(0);
    while(!s.empty())
    {
        int x=*s.begin();
        s.er(x);
        for(auto y:v[x])
        {
            ll t=d[x]+1;
            ll c=y.ss/t;
            if (t*t<y.ss) t=sqrt(y.ss);
            t=max(t,d[x]+1);
            c=y.ss/t;
            ll len=y.sf+c+t-1;
            int k=6;
            while(c)
            {
                k--;
                if (!k) break;
                len=min(len,y.sf+c+t-1);
                t=y.ss/c+1;
                c=y.ss/t;
            }
            len=min(len,y.sf+c+t-1);
            if (d[y.fi]>len)
            {
                s.er(y.fi);
                d[y.fi]=len;
                s.in(y.fi);
            }
        }
    }
    if (d[n-1]==inf) d[n-1]=-1;
    cout<<d[n-1];
}
