#include <bits/stdc++.h>
#define INF INT_MAX
#define x first
#define y second
#define nmax 50000 + 1

using namespace std;

int n, m;
int dist[ nmax ];
int nrv[ nmax ];
int inc[ nmax ];

vector < pair < int, int > > v[ nmax ];

int bellman(){
    queue < int > dx;
    dx.push( 1 );

    while (!dx.empty() && nrv[ dx.front() ]< n ){
        int nod = dx.front();
        dx.pop();

        inc[ nod ] = 0;

        for (auto it : v[ nod ]){
            if (dist[ nod ] + it.y < dist[ it.x ]){
                dist[ it.x ] = dist[ nod ] + it.y;

                if (inc[ it.x ] == 0){
                    inc[ it.x ] = 1;
                    dx.push(it.x);
                    nrv[ it.first ]++;
                }
            }
        }
    }
    return dx.size();
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");

    cin >> n >> m;

    for (int i = 1; i <= m; i++){

        int A, B, C;
        cin >> A >> B >> C;

        v[ A ].push_back({B, C});
    }

    for (int i = 1; i <= n; i++){
        dist[ i ] = INF;
        nrv[ i ] = inc[ i ] = 0;
    }

    dist[ 1 ] = 0;
    nrv[ 1 ] = inc[ 1 ] = 1;

    if (bellman() != 0)
        cout << "Ciclu negativ!";
    else
        for (int i = 2; i <= n; i++)
          cout << dist[ i ] << " ";
}