4. Odporné psiská, FUJ!

Dog Show Winner má veľmi rád svojho krásneho KSPsíka a vyhrávanie psích prehliadok. Čo však nemá rád, sú iné psy. Ustavične očuchávajú jeho miláčika. Nanešťastie pre neho sú psy v jeho rodnom meste veľmi obľúbené – sú doslova na každej ulici! Dog Show Winner je mimo iného veľmi excentrický. Každej ulici priradil číslo, podľa toho, ako veľmi bude jeho miláčik očuchaný, keď po nej prejde. A kedže je fakt veľmi excentrický, tak zisťuje ako veľmi bol jeho pes očuchaný bitovým OR-om. Na to aby mohol vyhrávať psie prehliadky, potrebuje chodiť na súťaže, ktoré sú všade v meste. Potrebuje teda nájsť také ulice v meste, aby sa pomocou nich vedel dostať kamkoľvek a zároveň aby bol jeho havko očuchaný čo najmenej. Sám to ale nezvládne a potrebuje vašu pomoc.

Úloha

Mesto reprezentujeme ako graf s ováhovanými hranami. Vašou úlohou je vybrať také hrany, aby graf zostal súvislý a jeho OR bol najmenší možný. Medzi dvomi vrcholmi vedie najviac jedna hrana. Graf je vo všetkých vstupoch súvislý.

Formát vstupu

Na prvom riadku vstupu dostanete dve čísla – počet vrcholov \(v\) a počet hrán \(e\). Nasleduje \(e\) riadkov po troch číslach. V \(i\)-tom riadku sú čísla \(x_i\), \(y_i\) a \(w_i\) – vrcholy, ktoré spája \(i\)-ta hrana a jej váha. Vrcholy indexujeme od 0.

V sadách platia nasledovné obmedzenia:

Formát výstupu

Vypíšte jedno číslo – najmenší možný bitový OR kostry grafu zadaného na vstupe.

Príklady

Input:

4 5
1 0 10
0 2 4
0 3 4
3 1 4
2 1 7

Output:

4

Keď si zoberieme hrany medzi 0 a 2, 0 a 3, 3 a 1 dostaneme súvislý graf s najmenším možným bitovým OR-om.

Input:

2 1
0 1 3

Output:

3

Musíme zobrať všetky hrany v grafe (čiže tú jednu), aby bol súvislý.