Rezolvare PBinfo #4357

Premierul Marii Britanii, Rishi Sunak, a decis să reorganizeze structura administrativă a comitatului Oxfordshire. În Oxfordshire sunt prezente N orașe numerotate de la 1 la N, conectate prin M autostrăzi (drumuri unidirecționale ce conectează două orașe). Rishi a hotărât ca toate orașele cu proprietatea că cetățenii tuturor celorlalte orașe pot ajunge în ele prin intermediul autostrăzilor să devină reședințe. Deoarece numărul de orașe și autostrăzi din Oxfordshire este foarte mare, Rishi vă cere ajutorul în rezolvarea a două probleme cheie.

Cerința

1. Care sunt indicii orașelor reședință din Oxfordshire.
2. Care este distanța minimă de la fiecare oraș până la cea mai apropiată reședință de acel oraș.

Date de intrare

Intrarea standard conține pe prima linie trei numere C, N și M, separate printr-un spațiu, unde C reprezintă numărul cerinței, N numărul de orașe și M numărul de autostrăzi. Pe următoarele M linii se află câte trei numere i, j și d, separate prin spații, reprezentând descrierea autostrăzilor: există o autostradă de la orașul cu indicele i până la orașul cu indicele j cu lungimea d.

Date de ieșire

Ieșirea standard va conține o singură linie. Dacă C = 1, se vor afișa indicii reședințelor, ordonați crescător, separați prin spații. Dacă C = 2, se vor afișa N numere, separate prin spații, reprezentând distanțele minime de la fiecare oraș (cu indici de la 1 la N) până la cea mai apropiată reședință de orașul respectiv (dacă orașul este reședință se va afișa 0).

Restricții și precizări

• 2 ≤ N ≤ 100.000
  • 1 ≤ M ≤ min(N ∗ (N − 1), 200.000)
  • 1 ≤ d ≤ 10.000
  • nu există o autostradă care să conecteze un oraș cu el însuși
  • nu există mai multe autostrăzi care să conecteze aceleași două orașe în același sens
  • în toate testele există cel puțin o reședință

Exemplul 1:

Intrare

1 6 6
4 3 2
2 4 4
4 2 2
5 4 6
6 2 7
1 3 10

Ieșire

3

Explicație

Orașul cu indicele 3 este singura reședință deoarece este singurul oraș în care se poate ajunge din toate celelalte orașe (vezi Figura 1).

Exemplul 2:

Intrare

2 9 12
8 4 30
4 6 16
6 1 13
6 5 1
5 2 26
7 2 10
3 9 23
9 3 5
1 4 7
4 5 18
2 5 8
9 2 19

Ieșire

24 0 42 17 0 1 10 47 19

Explicație

Sunt două reședințe: orașele cu indicii 2 și 5. Orașele cu indicii 1, 4, 6 și 8 sunt mai aproape de reședința cu indicele 5. Orașele cu indicii 3, 7 și 9 sunt mai aproape de reședința cu indicele 2. (vezi Figura 2).