Problem Statement

Planet Iwai consists of towns $1,\ \dots ,\ N$ and special roads $1,\ \dots,\ M$. By using road $i$, you can travel from town $X_i$ to any one of towns $L_i$ through $R_i$, taking $C_i$ minutes.

On Planet Iwai, whether there exists an algorithm that efficiently finds the shortest travel time between two towns had long been an open question. However, 29-year-old Iwai Seijin claims to have invented an algorithm that finds the shortest travel time from town $1$ to town $N$, named it the "Iwaijkstra Method", and published a paper on it.

Iwaijkstra Method

Let $\mathrm{que}$ be a priority queue, and add the pair of numbers $(0,1)$ to it
Let $\mathrm{dist}$ be an array of length $N$; assign 0 to $\mathrm{dist}_1$ and $\inf$ to all other elements
Let $\mathrm{vis}$ be an array of length $N$, and assign false to all elements
Repeat until $\mathrm{que}$ is empty:
Among the pairs of numbers in $\mathrm{que}$, store as $(a,b)$ one of the pairs whose left element is the smallest (if there are multiple such pairs, one whose right element is also the smallest among them)
Remove one pair of numbers $(a,b)$ from $\mathrm{que}$
For all i such that $\mathrm{dist}_i < a$, assign true to $\mathrm{vis}_i$
If $\mathrm{dist}_b = a$:
For all $j$ such that $X_j = b$, and for all $k$ such that $L_j \leq k \leq R_j$, if $\mathrm{vis}_k =\ $false:
Assign $\min(\mathrm{dist}_k,a+C_j)$ to $\mathrm{dist}_k$, and add the pair of numbers $(a+C_j,k)$ to $\mathrm{que}$
Output $\mathrm{dist}_N$

Iwai Seijin can complete almost all operations in an instant, but he has noticed that the one exception, the process of removing from $\mathrm{que}$, takes time because it is very complicated.

On behalf of Iwai Seijin, find how many times removal from $\mathrm{que}$ is performed when this algorithm is run on Planet Iwai. However, if this number exceeds $10^{18}$, or if this algorithm does not terminate, print Too Many.

Implementation Examples of the Iwaijkstra Method

#include <bits/stdc++.h>
using namespace std;

long long iwaijkstra(int n, int m, vector<int> x, vector<int> l, vector<int> r, vector<int> c){
	multiset<pair<long long, int>> que;
	que.emplace(0, 1);
	vector<long long> dist(n, 1e18), vis(n);
	dist[0] = 0;
	long long ans(0);
	while(!que.empty()){
		auto [a, b] = *que.begin();
		que.erase(que.begin()), ++ans;
		for (int i(0); i < n; ++i) if (dist[i] < a) vis[i] = true;
		if (vis[b - 1]) continue;
		for (int i(0); i < m; ++i) if (x[i] == b){
			for (int j(l[i] - 1); j < r[i]; ++j) if (!vis[j]) {
			    dist[j] = min(dist[j], a + c[i]);
			    que.emplace(a + c[i], j + 1);
			}
		}
	}
	cout << ans << endl;
	return dist.back();
}

import heapq

def iwaijkstra(n,m,x,l,r,c):
    que = []
    heapq.heappush(que, (0, 1))
    dist = [10 ** 18] * n
    dist[0] = 0
    vis = [False] * n
    ans = 0
    while len(que) > 0:
        a, b = que[0]
        heapq.heappop(que)
        ans += 1
        for i in range(n):
            if dist[i] < a:
                vis[i] = True
        if vis[b-1]: continue
        for i in range(m):
            if x[i] == b:
                for j in range(l[i] - 1, r[i]):
                    if not vis[j]:
                        dist[j] = min(dist[j], a + c[i])
                        heapq.heappush(que, (a + c[i], j + 1))
    print(ans)
    return dist[n-1]

Constraints

• $1 \le N,M \le 10^5$
• $1 \le X_i \le N$
• $1 \le L_i \le R_i \le N$
• $0 \le C_i \le 10^9$
• All inputs are integers
• Every vertex is reachable from vertex 1

Input

$N\ M$
$X_1\ L_1\ R_1\ C_1$
$\vdots$
$X_M\ L_M\ R_M\ C_M$

Output

Print a newline at the end.

Sample

Sample 1

Input

7 4
1 2 4 2
2 5 5 1
3 6 6 8
4 7 7 1

Output

7

The towns and roads of Planet Iwai can be represented as the following graph.

In this graph, the edge colors correspond to the road numbers as follows: red is 1, green is 2, blue is 3, and yellow is 4.

Sample 2

Input

6 4
1 4 6 1
4 2 3 0
3 5 6 8
2 3 3 0

Output

11

The correspondence between edge colors and road numbers is the same as in Sample 1.

6 7
1 1 6 4
1 1 6 0
2 4 4 0
4 6 6 0
6 3 3 0
3 5 5 0
5 2 2 0

Too Many

20 19
1 2 20 0
2 3 20 0
3 4 20 0
4 5 20 0
5 6 20 0
6 7 20 0
7 8 20 0
8 9 20 0
9 10 20 0
10 11 20 0
11 12 20 0
12 13 20 0
13 14 20 0
14 15 20 0
15 16 20 0
16 17 20 0
17 18 20 0
18 19 20 0
19 20 20 0

524288