Doprogramovanie do: 26. apríl 2024 23:59
3 dni
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

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:

Sada 1 2 3 4
\(2 \leq v \leq\) \(10\) \(1\,000\) \(10^4\) \(10^5\)
\(1 \leq e \leq\) \(19\) \(1\,000\) \(10^4\) \(10^5\)
\(0 \leq \max w_i \leq\) \(1\,000\) \(10^4\) \(10^6\) \(2*10^9\)

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ý.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.