#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct edge{
int x,y,c;
}
edges[250003];
int d[100003];
int n,m,i,j;
bool bellmanford(int s)
{
    for(i=1;i<=n;i++)
        if (i!=s)
            d[i] = 1<<30;
        else
            d[i] = 0;
    for(i=1;i<n;i++)
        for(j=0;j<m;j++)
            if (d[edges[j].x] + edges[j].c < d[edges[j].y])
               d[edges[j].y] = d[edges[j].x] + edges[j].c;
            d[edges[j].y]=edges[j].x+edges[j].c;
     for(j=0;j<m;j++)
       if (d[edges[j].x] + edges[j].c < d[edges[j].y])
           return false;
    return true;
}
int main()
{
    int s = 1;
    in>>n>>m;
    for(i=0;i<m;i++)
        in>>edges[i].x>>edges[i].y>>edges[i].c;
    if(bellmanford(s))
        for(i=2;i<=n;i++)
            out<<d[i]<<" ";
    else
        out<<"Ciclu negativ!";
    return 0;
}