#include <fstream>
#include <vector>
#include <queue>
#define f in
#define g out

using namespace std;
ifstream in ( "bellmanford.in" );
ofstream out( "bellmanford.out" );
int n, m, i, x, y, c, nod, vecin, cost;
vector< pair<int, int> > L[50500];
queue<int> q;
int d[50500], fr[50500], viz[50500];

int main() {
    f>>n>>m;
    for ( i=1; i <= m; i++ ){
        f>>x>>y>>c;
        L[x].push_back({y,c});
        L[y].push_back({x,c});
    }
    for ( i=2; i <= n; i++ )
        d[i]=2000000000;
    fr[1] = viz[1] = 1;
    q.push(1);
    while ( !q.empty() ) {
        nod = q.front();
        for ( auto x: L[nod] ){
            vecin = x.first;
            cost = x.second;
            if ( d[nod]+cost < d[vecin] ){
                d[vecin] = d[nod]+cost;
                if ( !viz[vecin] ){
                    fr[vecin]++;
                    viz[vecin] = 1;
                    q.push(vecin);
                    if ( fr[vecin] == n ){
                        g<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        viz[nod] = 0;
        q.pop();
    }
    for ( i=1; i <= n; i++ )
        g<<d[i]<<" ";
    
    return 0;
}