#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
#define inf 200000000

vector <int> A[50001];
vector <int> C[50001];
queue <int> Q;
int d[50001], incoada[50001], nrv[50001];
int n, m;

int main()
{
    int i, j, k, x, y, c, p, u;
    f >> n >> m;
    for( i = 1; i <= m; i++ ){
        f >> x >> y >> c;
        A[x].push_back(y);
        C[x].push_back(c);
    }

    for( i = 1; i <= n; i++ )
        d[i] = inf;
    d[1] = 0;

    Q.push(1);
    incoada[1] = 1;
    nrv[1] = 1;
    while( !Q.empty() ){
        i = Q.front();
        incoada[i] = 0;
        Q.pop();
        for( j = 0; j < A[i].size(); j++ )
            if( d[i] != inf && d[A[i][j]] > d[i] + C[i][j] ){
                d[A[i][j]] = d[i] + C[i][j];
                if( incoada[A[i][j]] == 0 ){
                    incoada[A[i][j]] = 1;
                    Q.push(A[i][j]);
                    nrv[A[i][j]]++;
                    if( nrv[A[i][j]] > n ){
                        g << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
    }

    for( i = 2; i <= n; i++ )
        g << d[i] << " ";

    return 0;
}