#include <fstream>
#include <queue>
#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];

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

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

int main(  ) {
    fin>>n>>m;
    for ( int i= 1; i<=m; ++i ) {
        int x, y, z;
        fin>>x>>y>>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;
}