Busy Beaver는 MIT의 지하 캠퍼스를 탐험하고 있습니다. $1$부터 $N$까지 번호가 매겨진 $N$개의 건물과, 특정 건물 쌍을 연결하는 $1$부터 $M$까지 번호가 매겨진 $M$개의 터널이 있습니다. $i$번째 터널은 건물 $a_i$와 $b_i$를 연결합니다. 터널에 들어가려면 먼저 $c_i$만큼의 코인을 지불해야 합니다. 하지만 터널을 통과하고 그 안의 예술을 감상한 후에는 $r_i$만큼의 코인을 보상으로 받습니다.

Busy Beaver는 건물 $1$에 살고 있으며 건물 $N$에서 열리는 강의에 참석할 예정입니다. Busy Beaver가 건물 $N$에 도달하기 위해 가지고 있어야 하는 최소 코인 개수는 얼마입니까?

다음 사항을 유의하십시오:

• 터널은 어느 방향으로든 원하는 횟수만큼 통과할 수 있습니다. 통과할 때마다 비용이 발생하고 보상을 받습니다.
• Busy Beaver는 보상으로 받은 코인을 향후 입장료를 지불하는 데 사용할 수 있습니다.
• 두 건물 사이에 하나 이상의 터널이 있을 수 있습니다.
• 코인 개수는 항상 $0$ 이상이어야 합니다.

입력

첫 번째 줄에는 두 개의 정수 $N$과 $M$이 공백으로 구분되어 주어집니다 ($2\le N \le 10^5$, $1\le M \le 2\cdot 10^5$).

다음 $M$개의 줄은 터널에 대한 정보를 설명합니다. 각 줄은 네 개의 정수 $a_i, b_i, c_i, r_i$로 구성되며 공백으로 구분됩니다 ($1 \le a_i,b_i \le N$, $a_i \ne b_i$, $0 \le c_i,r_i \le 10^9$).

건물 $N$은 유한한 개수의 코인을 가지고 시작하면 건물 $1$에서 도달할 수 있음이 보장됩니다.

출력

정답을 한 줄에 출력하십시오.

서브태스크

• ($20$점) $N-1$개의 터널이 존재합니다: 모든 $1 \le i < N$에 대해 건물 $i$와 건물 $i+1$을 연결하는 터널이 하나씩 있습니다.
• ($20$점) 모든 $1 \le i \le M$에 대해 $r_i = 0$입니다.
• ($20$점) 모든 $1 \le i \le M$에 대해 $c_i = r_i$입니다.
• ($20$점) 모든 $1 \le i \le M$에 대해 $c_i \ge r_i$입니다.
• ($20$점) 추가 제약 조건 없음.

예제

입력 1

3 3
1 2 2 1
2 3 3 0
1 3 5 0

출력 1

4

입력 2

4 3
1 2 3 1
2 3 1 2
3 4 2 4

출력 2

3

입력 3

3 4
1 2 4 3
1 2 4 6
2 1 5 4
2 3 10 9

출력 3

4

참고

예제 설명 1

Busy Beaver가 $4$개의 코인을 가지고 시작하면, 먼저 건물 $1$에서 건물 $2$로 가는 터널을 통과하여 $2$개의 코인을 지불하고 $1$개의 코인을 돌려받습니다(건물 $2$에 도착했을 때 $4-2+1=3$개의 코인을 가짐). 그 후 $3$개의 코인을 사용하여 건물 $2$에서 건물 $3$으로 가는 터널을 통과할 수 있습니다.

예제 설명 2

Busy Beaver가 $3$개의 코인을 가지고 시작하면, 먼저 건물 $1$에서 건물 $2$로 가는 터널을 통과하여 도착 시 $1$개의 코인을 가집니다. 그 후 건물 $3$으로 이동하면 $2$개의 코인을 가지게 됩니다. 마지막으로 $2$개의 코인을 지불하고 $4$개의 코인을 돌려받으며 건물 $4$에 도착할 수 있습니다.

예제 설명 3

Busy Beaver는 건물 $1$에서 $4$개의 코인을 가지고 시작하여, 터널 $2$를 $3$번 통과하고, $10$개의 코인으로 터널 $4$에 진입하여 $9$개의 코인을 가진 채 건물 $3$에 도착할 수 있습니다. Busy Beaver가 $4$개 미만의 코인을 가지고 시작해서는 건물 $3$에 도달할 수 없음이 증명될 수 있습니다.