#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

#define nMax 50010
#define infinit 200000000

using namespace std;

class muchii{
public:
    int catre;
    int cost;
};

int n;
vector <muchii> graf[nMax];
int distante[nMax];
int folosit[nMax];
queue <int> q;

void citire()
{
    int m;
    scanf ("%d", &n);
    scanf ("%d", &m);
    while (m --){
        muchii x;
        int y;
        scanf ("%d %d %d", &y, &x.catre, &x.cost);
        graf[y].push_back (x);
    }
}

void bellmanford (int x){
    for (int i = 0; i <= n; ++ i){
        distante[i] = infinit;
    }
    distante[x] = 0;
    q.push (x);
    while (!q.empty ()){
        x = q.front ();
        q.pop ();
        folosit[x] ++;
        if (folosit[x] == n){
            printf ("Ciclu negativ!\n");
            exit(0);
        }
        for (unsigned int i = 0; i < graf[x].size (); ++ i){
            if (distante[graf[x][i].catre] > distante[x] + graf[x][i].cost){
                distante[graf[x][i].catre] = distante[x] + graf[x][i].cost;
                q.push(graf[x][i].catre);
            }
        }
    }
}

void afis()
{
    for (int i = 2; i <= n; ++ i){
        printf ("%d ", distante[i]);
    }
    printf ("\n");
}

int main()
{
    freopen ("bellmanford.in", "r", stdin);
    freopen ("bellmanford.out", "w", stdout);

    citire();
    bellmanford(1);
    afis();

    return 0;
}