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

using namespace std;

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

const long long INFINIT =999999999;
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 read()
{
    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()
{
    read();
    bellmanford();
    if (ciclu_negativ)
        fout << "Ciclu negativ!";
    else
        for (int i = 2; i <= N; i++)
            fout << dist[i] << ' ';
    return 0;
}