Ordinamento dei tunnel spazio-temporali#9601
Le mucche di Farmer John sono stanche della sua richiesta quotidiana di ordinarsi prima di lasciare la stalla ogni mattina. Hanno appena conseguito il dottorato di ricerca in fisica quantistica e sono pronte a velocizzare un po' questo processo.
Questa mattina, come al solito, le mucche di Farmer John, comodamente numerate da , si trovano nella stalla in posizioni diverse, anch'esse numerate da , dove la mucca si trova nella posizione p_i. Tuttavia, questa mattina nella stalla ci sono anche tunnel spazio-temporali, numerati da . Il tunnel collega bidirezionalmente le posizioni a_i e b_i e ha larghezza w_i.
In qualsiasi momento, due mucche che si trovano alle estremità opposte di un tunnel possono scambiarsi simultaneamente di posto, spostandosi attraverso quel tunnel. Le mucche devono effettuare tali scambi finché, per ogni 1 \leq i \leq n, la mucca non si trovi nella posizione .
Le mucche non vogliono rimanere bloccate in tunnel troppo stretti. Aiutale a massimizzare la larghezza minima tra tutti i tunnel che dovranno utilizzare per ordinarsi.
Nella prima riga si trovano due numeri interi n~(1 \le n \le 10^5) e m~(1 \le m \le 10^5).
Nella seconda riga si trovano numeri interi p_1, p_2, \ldots, p_n. È garantito che sia una permutazione dei numeri .
Per ogni da a , nella riga i + 2 si trovano i numeri interi a_i, b_i e w_i~(1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le w_i \le 10^9).
Stampa un singolo numero intero: il massimo valore possibile della larghezza minima tra tutti i tunnel utilizzati nel processo di ordinamento. Se le mucche non hanno bisogno di utilizzare alcun tunnel per ordinarsi, stampa .
Ecco uno dei possibili modi per ordinare le mucche utilizzando solo tunnel di larghezza almeno :
La mucca e la mucca si scambiano di posto usando il terzo tunnel.
La mucca e la mucca si scambiano di posto usando il primo tunnel.
La mucca e la mucca si scambiano di posto usando il terzo tunnel.
Esempio 1
Esempio 2