#include<fstream>
#include<vector>

using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

const int N = 50003;
const int M = 100003;
const int inf = 1e9;

int n,m,i,j,a,b,c;

#define pb push_back
#define mp_make_pair

struct edge
{
    int a,b,cost;
};


vector< edge > g(M);

vector< int > d (N,inf);
vector< int > p (N, -1);



void Read()
{
     cin >> n >> m;
     for (i=0;i<m;i++)
        cin >> a >> b >> c,
         g[i].a = a, g[i].b = b, g[i].cost = c;
}

void Bellman_Ford(int s)
{
    d[s] = 0;
    int x=0;
    for (i=0;i<n;i++)
    {
        x = 0;
        for (j=0;j<m;j++)
            if (d[g[j].a]<inf)
             if (d[g[j].b]>d[g[j].a]+g[j].cost)
               d[g[j].b]=max(-inf,d[g[j].a]+g[j].cost),
               x=1;
        if (!x) break;
    }
    if (x) {
        cout << "Ciclu negativ!";
        return ;
    }
    for (i=2;i<=n;i++)
        cout << d[i] << ' ';
}


int main()
{
    Read();
    Bellman_Ford(1);
    return 0;
}