#include <stdio.h>
#include <vector>
#include <queue>

#define INF 1e9
#define MMAX 250005
#define NMAX 50005

using namespace std;

FILE *fin = fopen("bellmanford.in", "r");
FILE *fout = fopen("bellmanford.out", "w");

int n,m,i,dist[NMAX],much,used[MMAX],x;
bool incoada[NMAX],ok;

struct muchie {int x; int y; int cost;} muchii[MMAX];
vector <int> graf[NMAX];
queue <int> q;

int main()
{
    fscanf(fin, "%d%d", &n,&m);
    for(i=1; i<=m; ++i)
    {
        fscanf(fin, "%d%d%d", &muchii[i].x,&muchii[i].y,&muchii[i].cost);
        graf[muchii[i].x].push_back(i);
    }

    for(i=1; i<=n; ++i)
        dist[i] = INF;
    dist[1] = 0;

    q.push(1);
    incoada[1] = true;
    ok = true;
    while(!q.empty() and ok)
    {
        x = q.front();

        for(i=0; i<graf[x].size(); ++i)
        {
            much = graf[x][i];
            if(dist[x] + muchii[much].cost < dist[muchii[much].y])
            {
                dist[muchii[much].y] = dist[x] + muchii[much].cost;

                if(!incoada[muchii[much].y])
                {
                    q.push(muchii[much].y);
                    incoada[muchii[much].y] = true;
                    used[much]++;
                    if(used[much] > n)
                        ok = false;
                }//if incoada
            }//if
        }//for i

        incoada[x] = false;
        q.pop();
    }//while

    if(ok)
        for(i=2; i<=n; ++i)
            fprintf(fout, "%d ", dist[i]);
    else
        fprintf(fout, "Ciclu negativ!");

    fclose(fin);
    fclose(fout);
    return 0;
}