#include <fstream>
#include <queue>
#include <climits>
#include <vector>
#include <iostream>
#include <climits>

using namespace std;

#define nmax 50000
vector<pair<int, int> > graph[nmax];
int d[nmax];
int n, m;
int v[nmax];

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

void read_data() {
    f >> n >> m;
    for(int i = 0; i < m; i++) {
        int x, y, z;
        f >> x >> y >> z;
        graph[x].push_back( make_pair(y, z) );
    }
}

void bellman_ford() {
    for( int i = 2; i <= n; i++) d[i] = INT_MAX;

    queue <int > coada;
    coada.push(1);

    while( !coada.empty() ) {
        int nod = coada.front(); coada.pop();

        if( v[nod] > n - 1 ) {
            g << "Ciclu negativ!\n";
            return 0;
        }

        v[nod]++;
        for( auto x: graph[nod] ) {
            int di = x.second;
            int no = x.first;
            if( d[no] > d[nod] + di ) {
                d[no] = d[nod] + di;
                coada.push(no);
            }
        }
    }

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


int main() {
    read_data();
    bellman_ford();
    return 0;
}