#include <fstream>
#include <vector>
#include <queue>
#define inf 1<<30
#define N 50003
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,dist[N],use[N],y,c,i,x;
struct arc{int nod,cost;}v;
vector <arc> L[N];
vector <arc> :: iterator it,sf;
queue <int> Q;
int main(){
    f>>n>>m;
    for(i=1;i<=m;i++){   f>>x>>v.nod>>v.cost; L[x].push_back(v);}
    for(i=2; i<=n; i++) dist[i]=inf;
    Q.push(1);
    while(!Q.empty()){
        x=Q.front(); Q.pop();
        use[x]++;
        if(use[x]==n) {g<<"Ciclu negativ!\n"; return 0;}
        for(auto &y:L[x])
        {
            if(dist[y.nod]>dist[x]+y.cost){
                dist[y.nod]=dist[x]+y.cost;
                Q.push(y.nod);
            }
        }
    }
    for(i=2; i<=n; i++) g<<dist[i]<<" ";
    g<<"\n";  return 0;
}