#include <fstream>
#include <queue>
#include <vector>
 
using namespace std;
 
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
 
const long long INFINIT = INT32_MAX;
const int NMAX = 50005;
 
long long dist[NMAX];
vector < pair <int, int> > weighted_edges[NMAX];
queue < int > nodes;
bool inqueue[NMAX];
int aparitii[NMAX];
 
int N, M;
bool ciclu_negativ = false;
 
void citire()
{
    fin >> N >> M;
    int x, y, z;
    for (int i = 0; i < M; i++)
    {
        fin >> x >> y >> z;
        weighted_edges[x].push_back( {y, z} );
    }
}
 
void bellmanford()
{
    for (int i = 1; i <= N; i++)
        dist[i] = INFINIT;
    dist[1] = 0;
    nodes.push(1);
    inqueue[1] = true;
 
    while(!nodes.empty() && !ciclu_negativ)
    {
        int top = nodes.front();
        for(unsigned int i = 0; i < weighted_edges[top].size(); i++)
        {
            int u = top;
            int v          = weighted_edges[top][i].first;
            long long cost = weighted_edges[top][i].second;
            if (dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                if (!inqueue[v])
                {
                    nodes.push(v);
                    inqueue[v] = true;
                }
                aparitii[v]++;
                if (aparitii[v] == N)
                    ciclu_negativ = true;
            }
        }
        nodes.pop();
        inqueue[top] = false;
    }
}
 
int main()
{
    citire();
    bellmanford();
    if (ciclu_negativ)
        fout << "Ciclu negativ!";
    else
        for (int i = 2; i <= N; i++)
            fout << dist[i] << ' ';
    return 0;
}