#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}
void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}
void ioinit() { cout << fixed << setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }
// clang-format on

struct edge {
    int v;
    ll cost;
};
struct edg2 {
    int v;
    ll c;
    ll d;
};
class greater_cost {
   public:
    bool operator()(const edge& lh, const edge& rh) const {
        return lh.cost > rh.cost;
    }
};
using pq_mincost = priority_queue<edge, vector<edge>, greater_cost>;

const ll LG = 1e17;
vector<vector<edge>> edgcost;
vector<vector<edg2>> edgs;
vector<ll> c;
vector<ll> d;
ll dijkstra() {
    ll n = edgs.size();
    vector<bool> done(n, false);
    pq_mincost pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        ll cost = e.cost;
        int u = e.v;
        if (done[u]) continue;
        done[u] = true;

        if (u == n - 1) {
            return cost;
        }
        for (auto v : edgs[u]) {
            ll left = cost;
            ll right = LG;
            while (right - left >= 3) {
                ll t1 = left + (right - left) / 3;
                ll t2 = left + 2 * (right - left) / 3;
                double x1 = t1 + v.c + double(v.d) / (t1 + 1);
                double x2 = t2 + v.c + double(v.d) / (t2 + 1);

                if (x1 <= x2) {
                    right = t2;
                } else {
                    left = t1;
                }
            }
            ll nc = INF;
            for (ll t = max(left - 2, cost); t <= right + 2; t++) {
                ll x = t + v.c + v.d / (t + 1);
                nc = min(nc, x);
            }
            pq.push({v.v, nc});
        }
    }
    return -1;
}
int main() {
    // ダイクストラで三分探索(!?)
    ioinit();
    ll n, m;
    cin >> n >> m;
    edgcost.resize(n);
    edgs.resize(n);
    c.resize(m);
    d.resize(m);
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b >> c[i] >> d[i];
        a--;
        b--;
        edgs[a].push_back({int(b), c[i], d[i]});
        edgs[b].push_back({int(a), c[i], d[i]});
    }
    ll ans = dijkstra();
    print(ans);
}


#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/trie_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define ll 				long long int
#define ld				long double
#define mod             1000000007
#define inf             1e18
#define endl			"\n"
#define pb 				push_back
#define vi              vector<int>
#define vl              vector<ll>
#define vs				vector<string>
#define pii             pair<ll,ll>
#define ump				unordered_map
#define mp 				make_pair
#define pq_max          priority_queue<ll>
#define pq_min          priority_queue<ll,vi,greater<ll> >
#define all(n) 			n.begin(),n.end()
#define ff 				first
#define ss 				second
#define mid(l,r)        (l+(r-l)/2)
#define bitc(n) 		__builtin_popcount(n)
#define loop(i,a,b) 	for(int i=(a);i<=(b);i++)
#define looprev(i,a,b) 	for(int i=(a);i>=(b);i--)
#define iter(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define log(args...) 	{ string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define logarr(arr,a,b)	for(int z=(a);z<=(b);z++) cout<<(arr[z])<<" ";cout<<endl;
#define M 		1000000007
#define w(x)            int x; cin>>x; while(x--)
template <typename T> T gcd(T a, T b) {if (a % b) return gcd(b, a % b); return b;}
template <typename T> T lcm(T a, T b) {return (a * (b / gcd(a, b)));}
vs tokenizer(string str, char ch) {std::istringstream var((str)); vs v; string t; while (getline((var), t, (ch))) {v.pb(t);} return v;}


void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << endl;
	err(++it, args...);
}
//typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
//typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> pbtrie;



void file_i_o()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

const int N = 2e5 + 5;

vi v(N);

class union_find
{

public:
	int *pr;
	int *sz;

	union_find(int n)
	{
		pr = new int[n + 1];
		sz = new int[n + 1];

		for (int i = 1; i <= n; ++i)
			pr[i] = i, sz[i] = 1;
	}

	int root(int i)
	{
		if (pr[i] == i)
			return i;

		return pr[i] = root(pr[pr[i]]);
	}

	int find(int i, int j)
	{
		return (root(i) == root(j));
	}

	int un(int i, int j)
	{
		int u = root(i);
		int v = root(j);

		if (u == v)
			return 0;

		if (sz[u] < sz[v])
			swap(u, v);

		pr[v] = u;
		sz[u] += sz[v];

		return 1;
	}
};



int main(int argc, char const *argv[]) {
	clock_t begin = clock();
	file_i_o();
	// Write your code here....
	int n;
	cin >> n;

	vi v(n);

	loop(i, 0, n - 1)cin >> v[i];

	union_find dsu(N);

	int s = 0, l = n - 1;
	int ans = 0;
	while (s < l) {

		int curr = dsu.un(v[s], v[l]);

		if (curr)ans++;

		s++;
		l--;

	}

	cout << ans << endl;

#ifndef ONLINE_JUDGE
	clock_t end = clock();
	cout << "\n\nExecuted In: " << double(end - begin) / CLOCKS_PER_SEC * 1000 << " ms";
#endif
	return 0;
}







