Plimbare

Time limit: 3s Memory limit: 64MB Input: plimbare.in Output: plimbare.out

Cerință

Gigi este un pasionat de plimbări cu mașina. Îi place foarte mult să se plimbe cu mașina între NN orașe. Aceste orașe sunt conectate de drumuri a căror lungime este cunoscută. Drumurile sunt bidirecționale (dacă există un drum de 55 km de la orașul AA la BB, atunci același drum poate fi folosit și de la BB la AA). 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 AA, și care se întoarce tot în orașul AA, dar fără să meargă pe același drum de 2 ori.

Cunoscând NN – numărul de orașe, MM – numărul de drumuri și descrierea celor MM drumuri în formatul (uu, vv și kk – reprezintă un drum de la uu la vv de cost kk) 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 NN și MM.
Pe următoarele M linii se găsesc câte trei numere uu, vv si costcost, 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 NN 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%30\% din teste, N10N \leq 10 și M15M \leq 15;
  • Pentru 100%100\% din teste, N2 000N \leq 2 \ 000 și M30 000M \leq 30 \ 000;
  • Costul unei rute nu va depăși 1 000 000 0001 \ 000 \ 000 \ 000;
  • Orașele sunt numerotate de la 00 la N1N - 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 00, drumul interesant de lungime minimă este 0-2-3-4-1-0 cu lungimea 1313.
Pentru nodul 11, drumul interesant de lungime minimă este 1-4-3-2-0-1 cu lungimea 1313.
Pentru nodul 22, drumul interesant de lungime minimă este 2-3-4-2 cu lungimea 77.
Pentru nodul 33, drumul interesant de lungime minimă este 3-2-4-3 cu lungimea 77.
Pentru nodul 44, drumul interesant de lungime minimă este 4-3-2-4 cu lungimea 77.

Log in or sign up to be able to send submissions!