h2. Date de intrare

Fişierul de intrare $bellmanford.in$ conţine pe prima linie numerele $N şi $M$ cu semnificaţia din enunţ. Pe următoarele $M$ linii se vor afla $3$ numere $A$, $B$ şi $C$ cu semnificaţia că există o muchie de cost $C$ de la nodul $A$ la nodul $B$.

Fişierul de intrare $bellmanford.in$ conţine pe prima linie numerele $N$ şi $M$ cu semnificaţia din enunţ. Pe următoarele $M$ linii se vor afla $3$ numere $A$, $B$ şi $C$ cu semnificaţia că există o muchie de cost $C$ de la nodul $A$ la nodul $B$.

h2. Date de ieşire

În fişierul de ieşire $bellmanford.out$ se va afişa pe prima linie mesajul "$Ciclu negativ!$" dacă în graf există un astfel de ciclu sau, în caz contrar, $N-1$ numere separate printr-un spaţiu. Al $i$-lea număr va reprezenta costul minim al unui drum minim de la nodul $1$ la nodul $i+1$.

În fişierul de ieşire $bellmanford.out$ se va afişa pe prima linie mesajul "$Ciclu negativ!$" dacă în graf există un astfel de ciclu sau, în caz contrar, $N-1$ numere separate printr-un spaţiu. Al $i$-lea număr va reprezenta costul minim al unui lant de la nodul $1$ la nodul $i+1$.

h2. Restricţii