oxford

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ă $2$ 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ţă

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

Se va citi din consolă. Datele de intrare conţin pe prima linie $3$ 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 $3$ 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

Se va afișa 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 \leq N \leq 10^5$;
• $1 \leq M \leq min(N * (N − 1), 2 * 10^5)$;
• $1 \leq d \leq 10^4$;
• 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ță;
• Subtask $1$, $20$ puncte: $C = 1$ și $N \leq 1 \ 000$;
• Subtask $2$, $40$ puncte: $C = 1$;
• Subtask $3$, $10$ puncte: $C = 2$ și $N \leq 1 \ 000$;
• Subtask $4$, $30$ puncte: $C = 2$.

Exemplul 1

stdin

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

stdout

3

Exemplul 2

stdin

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

stdout

24 0 42 17 0 1 10 47 19

Explicație

Pentru primul exemplu, 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).
Pentru al doilea exemplu, 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).