Busy Beaver explore le campus souterrain du MIT. Il y a $N$ bâtiments étiquetés $1,\dots,N$ et $M$ tunnels étiquetés $1,\dots,M$ reliant certaines paires de bâtiments. Le $i^\text{ème}$ tunnel relie les bâtiments $a_i$ et $b_i$. Afin d'y entrer, vous devez d'abord payer $c_i$ pièces. Cependant, après avoir traversé le tunnel et apprécié son art, vous êtes récompensé par $r_i$ pièces.

Busy Beaver vit dans le bâtiment $1$ et doit assister à son cours dans le bâtiment $N$. Quel est le nombre minimum de pièces qu'il doit apporter avec lui pour pouvoir atteindre le bâtiment $N$ ?

Gardez à l'esprit les points suivants :

• Les tunnels peuvent être traversés dans n'importe quelle direction, un nombre illimité de fois. Chaque fois que vous traversez un tunnel, les frais sont payés et la récompense est collectée.
• Busy Beaver peut utiliser les pièces qu'il reçoit en récompense pour payer les frais d'entrée futurs.
• Il peut y avoir plus d'un tunnel reliant deux bâtiments.
• Vous ne pouvez jamais avoir un nombre négatif de pièces.

Entrée

La première ligne contient deux entiers séparés par un espace, $N$ et $M$ ($2\le N \le 10^5$, $1\le M \le 2\cdot 10^5$).

Les $M$ lignes suivantes décrivent les tunnels. La $i^\text{ème}$ ligne consiste en quatre entiers séparés par des espaces, $a_i$, $b_i$, $c_i$ et $r_i$ ($1 \le a_i,b_i \le N$, $a_i \ne b_i$, $0 \le c_i,r_i \le 10^9$).

Il est garanti que le bâtiment $N$ est accessible depuis le bâtiment $1$ en commençant avec un nombre fini de pièces.

Sortie

Affichez une ligne contenant la réponse.

Sous-tâches

• ($20$ points) Il y a $N-1$ tunnels : un tunnel reliant le bâtiment $i$ au bâtiment $i+1$ pour tout $1 \le i < N$.
• ($20$ points) $r_i = 0$ pour tout $1 \le i \le M$.
• ($20$ points) $c_i = r_i$ pour tout $1 \le i \le M$.
• ($20$ points) $c_i \ge r_i$ pour tout $1 \le i \le M$.
• ($20$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

4

Entrée 2

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

Sortie 2

3

Entrée 3

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

Sortie 3

4

Remarque

Explication de l'exemple 1

Si Busy Beaver commence avec $4$ pièces, il peut d'abord traverser le tunnel du bâtiment $1$ au bâtiment $2$, en payant $2$ pièces et en recevant $1$ pièce en retour (il a donc $4-2+1=3$ pièces lorsqu'il arrive au bâtiment $2$), puis traverser le tunnel du bâtiment $2$ au bâtiment $3$ en utilisant ses $3$ pièces.

Explication de l'exemple 2

Si Busy Beaver commence avec $3$ pièces, il peut d'abord traverser le tunnel du bâtiment $1$ au bâtiment $2$, avec $1$ pièce lorsqu'il arrive. Ensuite, il peut aller au bâtiment $3$, après quoi il a $2$ pièces. Enfin, il peut atteindre le bâtiment $4$ en payant $2$ pièces et en recevant $4$ pièces lorsqu'il arrive.

Explication de l'exemple 3

Busy Beaver peut commencer dans le bâtiment $1$ avec $4$ pièces, traverser le tunnel $2$ trois fois, entrer dans le tunnel $4$ avec $10$ pièces, et arriver au bâtiment $3$ avec $9$ pièces. Il peut être démontré que Busy Beaver ne peut pas atteindre le bâtiment $3$ en commençant avec moins de $4$ pièces.