#include <fstream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int inf= 1<<30;
const int nmax= 50000;

struct str {
    int x, y;
}; 

queue <int> q;
vector <str> g[nmax+1];

string buffer;
string::iterator buffer_it;

int n, m;
int w[nmax+1];

inline str mp( int x, int y ) {
    str sol;
    sol.x= x, sol.y= y;
    return sol;
}

void read( int &x ) {
    for ( ; (*buffer_it<'0' || *buffer_it>'9') && *buffer_it!='-'; ++buffer_it ) ;
    int sign= 1;
    if ( *buffer_it=='-' ) {
        ++buffer_it, sign= -1;
    }
    
    for ( x= 0; *buffer_it>='0' && *buffer_it<='9'; ++buffer_it ) {
        x= x*10+*buffer_it-'0';
    }
    x*= sign;
}

int main(  ) {
    getline( fin, buffer, (char)0 );
    buffer_it= buffer.begin();

    read(n), read(m);
    for ( int i= 1; i<=m; ++i ) {
        int x, y, z;
        read(x), read(y), read(z);
        g[x].push_back( mp( y, z ) );
    }
    w[1]= 0;
    for ( int i= 2; i<=n; ++i ) w[i]= inf;
    
    for ( q.push(1); !q.empty(); q.pop() ) {
        int x= q.front();
        for ( int j= 0; j<(int)g[x].size(); ++j ) {
            if ( w[x]+g[x][j].y<w[g[x][j].x] ) {
                w[g[x][j].x]= w[x]+g[x][j].y;
                q.push(g[x][j].x);
            }
        }
    }

    int ok= 1;
    for ( int i= 1; i<=n && ok==1; ++i ) {
        for ( int j= 0; j<(int)g[i].size() && ok==1; ++j ) {
            if ( w[i]+g[i][j].y<w[g[i][j].x] ) {
                ok= 0;
                fout<<"Ciclu negativ!\n";
            }
        }
    }
    if ( ok==1 ) 
        for ( int i= 2; i<=n; ++i ) fout<<w[i]<<" ";
    fout<<"\n";

    return 0;
}