_Până şi Antonio a auzit de problema spectacolelor. Fiind însă o problemă deja foarte bine cunoscută şi mult prea "clasică" pentru gusturile lui Antonio, acesta vă propune să rezolvaţi următoarea problema a spectacolelor. Succes!_

Se dau $N$ săli de spectacole si $M$ spectacole. Pentru fiecare din cele $M$ spectacole se dau $3$ numere $s{~i~}$, $x{~i~}$ si $y{~i~}$ reprezentând sala unde se ţine spectacolul, timpul de început, respectiv timpul de sfârşit. Se ştie că pentru a se deplasa intre sali Antonio trebuie sa se deplaseze printr-un punct central, iar drumurule din acest punct central spre o sala si inapoi nu sunt identice. Mai exact durata de deplasare dinspre sala cu numarul $i$ si punctul central este $A{~i~}$, iar dinspre punctul central spre sala i este $B{~i~}$. Nu exista alta metoda pentru Antonio sa se deplaseze intre 2 sali $i$ si $j$, astfel pentru a se deplasa de la sala $i$ la sala $j$ Antonio are nevoie de $A{~i~} + B{~j~}$ momente de timp. Antonio vrea să vadă cât mai multe spectacole, respectând următoarele reguli:

Se dau $N$ săli de spectacole si $M$ spectacole. Pentru fiecare din cele $M$ spectacole se dau $3$ numere $s{~i~}$, $x{~i~}$ si $y{~i~}$ reprezentând sala unde se ţine spectacolul, timpul de început, respectiv timpul de sfârşit. Se ştie că pentru a se deplasa intre sali Antonio trebuie sa se deplaseze printr-o sală centrală, iar drumurile din această sală centrală spre o sală de spectacol şi drumurile inverse nu sunt identice. Mai exact durata de deplasare dinspre sala cu numarul $i$ si sala centrală este $A{~i~}$, iar dinspre sala centrală spre sala i este $B{~i~}$. Nu exista altă metoda pentru Antonio să se deplaseze între 2 sali $i$ şi $j$, astfel, pentru a se deplasa de la sala $i$ la sala $j$ Antonio are nevoie de $A{~i~} + B{~j~}$ momente de timp. Antonio vrea să vadă cât mai multe spectacole, respectând următoarele reguli:

* Antonio va vedea doar spectacole complete. Altfel spus, Antonio nu are voie să părăsească sala decât în momentul terminării spectacolului.