#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

#define oo 1 << 30

using namespace std;

struct edge{
    int x, y;
    short c;
};
vector< edge > E;

vector<int> L[50005];
int d[50005];
int t[50005];
bool used[50005];

vector< pair<int, int> > H;

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");

    int n, m;
    f >> n >> m;
    for(int i = 0; i < m; i ++) {
        edge aux;
        f >> aux.x >> aux.y >> aux.c;
        E.push_back(aux);
        L[aux.x].push_back(i);
    }

    for(int i = 2; i <= n; i ++)
        d[i] = oo;

    H.push_back(make_pair(0, 1));
    make_heap(H.begin(), H.end());

    long long maxx = 1LL * (n - 1) * m;
    while(H.size() > 0 && maxx) {
        maxx --;

        pop_heap(H.begin(), H.end());
        pair<int, int> aux = H.back();
        H.pop_back();

        int nod = aux.second;

        used[nod] = false;
        for(int j = 0; j < L[nod].size(); j ++) {
            int muc = L[nod][j];
            if(d[ E[muc].y ] > d[ E[muc].x ] + E[muc].c) {
                d[ E[muc].y ] = d[ E[muc].x ] + E[muc].c;
                t[ E[muc].y ] = E[muc].x;
                if(!used[ E[muc].y ]) {
                    used[ E[muc].y ] = true;
                    H.push_back( make_pair(- d[ E[muc].y ], E[muc].y) );
                    push_heap(H.begin(), H.end());
                }
            }
        }
    }



    for(int j = 0; j < m; j ++) {

        if(d[ E[j].y ] > d[ E[j].x ] + E[j].c) {
            g << "Ciclu negativ!\n";
            return 0;
        }
    }

    for(int i = 2; i <= n; i ++)
        g << d[i] << " ";
    g << "\n";
    return 0;
}