#define NMAX 50005
#include <cstdio>
#include <climits>
#include <vector>
#include <cstdlib>
#include <queue>
using namespace std;

int n, m;
int Dmin[NMAX], ap[NMAX], modifV[NMAX];
vector<pair<int, int>> graph[NMAX];
queue<int> Q;

void read()
{
    int x, y, c;

    scanf("%d %d", &n, &m);
    for(int i=0; i<m; ++i)
    {
        scanf("%d %d %d", &x, &y, &c);
        graph[x].push_back({y, c});
    }
}

void init()
{
    for(int i=2; i<=n; ++i)
        Dmin[i] = INT_MAX;
}

void solve()
{
    Q.push(1);
    ap[1] = 1;
    while(!Q.empty())
    {
        int t = Q.front();
        for(auto &v:graph[t])
            if(Dmin[v.first] > Dmin[t] + v.second)
            {
                Dmin[v.first] = Dmin[t] + v.second;
                modifV[v.first] ++;
                if(ap[v.first] == 0)
                {
                    Q.push(v.first);
                    ap[v.first] = 1;
                }
                if(modifV[v.first] >= n)
                {
                    printf("Ciclu negativ!");
                    exit(0);
                }
            }
        Q.pop();
        ap[t]--;
    }

}

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


int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    read();
    init();
    solve();
    write();
    return 0;
}