Simulation - Info-Oltenia 2024 Echipe XI-XII | Plimbare

Cerință

Gigi este un pasionat de plimbări cu mașina. Îi place foarte mult să se plimbe cu mașina între $N$ orașe. Aceste orașe sunt conectate de drumuri a căror lungime este cunoscută. Drumurile sunt bidirecționale (dacă există un drum de $5$ km de la orașul $A$ la $B$, atunci același drum poate fi folosit și de la $B$ la $A$). Chiar dacă Gigi este un pasionat, nu își dorește să petreacă toată ziua conducând. Pentru asta, el a găsit următoarea soluție: vrea să afle pentru fiecare oraș care este cea mai scurtă rută interesantă pe care o poate urma. O rută interesantă este definită ca o rută care pleacă dintr-un oraș, să îl numim $A$, și care se întoarce tot în orașul $A$, dar fără să meargă pe același drum de 2 ori.

Cunoscând $N$ – numărul de orașe, $M$ – numărul de drumuri și descrierea celor $M$ drumuri în formatul ($u$, $v$ și $k$ – reprezintă un drum de la $u$ la $v$ de cost $k$) se cere să îl ajutați pe Gigi să găsească cea mai scurtă rută interesantă pe care o poate avea, din fiecare oraș în parte.

Date de intrare

Pe prima linie a fișierului de intrare plimbare.in se găsesc $N$ și $M$.
Pe următoarele M linii se găsesc câte trei numere $u$, $v$ si $cost$, reprezentând descrierea fiecărei muchii.

Date de ieșire

Pe prima linie a fișierului de ieșire plimbare.out se vor găsi $N$ numere, care reprezintă lungimea minimă a unei rute interesante pentru fiecare oraș. Dacă nu există o rută interesantă pentru un oraș, atunci pentru orașul respectiv se va afișa -1.

Restricții și precizări

• Pentru $30\%$ din teste, $N \leq 10$ și $M \leq 15$;
• Pentru $100\%$ din teste, $N \leq 2 \ 000$ și $M \leq 30 \ 000$;
• Costul unei rute nu va depăși $1 \ 000 \ 000 \ 000$;
• Orașele sunt numerotate de la $0$ la $N - 1$.

Exemplu

plimbare.in

5 7        
0 1 5
0 2 4
1 2 14
1 4 1
4 2 4
4 3 2 
2 3 1

plimbare.out

13 13 7 7 7

Explicație

Pentru nodul $0$, drumul interesant de lungime minimă este 0-2-3-4-1-0 cu lungimea $13$.
Pentru nodul $1$, drumul interesant de lungime minimă este 1-4-3-2-0-1 cu lungimea $13$.
Pentru nodul $2$, drumul interesant de lungime minimă este 2-3-4-2 cu lungimea $7$.
Pentru nodul $3$, drumul interesant de lungime minimă este 3-2-4-3 cu lungimea $7$.
Pentru nodul $4$, drumul interesant de lungime minimă este 4-3-2-4 cu lungimea $7$.