#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct nod{
    int next, cost;
};

int N, M;

bool in[60000];
int best[60000], ap[60000];

queue < int > q;
vector < nod > g[60000];
vector < nod > :: iterator it;

int main()
{
    int i, x, y, c, node;
    nod aux;

    fin>>N>>M;

    for(i = 1; i <= M; i++)
    {
        fin>>x>>y>>c;

        aux.next = y;
        aux.cost = c;

        g[x].push_back(aux);
    }

    best[1] = 0;
    in[1] = true;

    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        in[node] = false;


        for( it = g[node].begin(); it != g[node].end(); it++)
        {
            if( best[it.next] > best[node] + it.cost )
            {
                best[it.next] = best[node] + it.cost;

                if( in[it.next] == false) {
                    if (ap[it.next] == N)
                    {
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                    ap[it.next]++;

                    q.push(it.next);
                    in[it.next] = true;
                }
            }
        }
    }

    for(i = 2; i <=N; i++)
        fout<<best[i]<<' ';

}