#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>

using namespace std;

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

const int inf = (1 << 30)-1 ;
int n , m , d[100001] , f[100001] , viz[100001] ;
int x , y , z ;
vector<pair<int, int>>g[100001] ;
deque<int>q ;

void init() {
    for(int i = 2 ; i<=n ; i++)
        d[i] = inf ;
}

bool ok = 1 ;
int bellman() {

    while(!q.empty()) {
        int nod = q.front() ;
        q.pop_front() ;
        viz[nod] = 0 ;

        for(auto y : g[nod]) {

            int vec = y.first ;
            int cost = y.second ;
            if(d[vec] > d[nod] + cost) {
                d[vec] = d[nod] + cost ;
                if(!viz[vec]) {
                    viz[vec] = 1 ;
                    f[vec]++ ;
                    q.push_back(vec) ;
                    if(f[vec] == n) {
                        fout << "Ciclu negativ!" ;
                        ok = 0 ;
                        return 0 ;
                    }
                }
            }
        }
    }
    return 1 ;
}


int main()
{
    fin >> n >> m ;
    for(int i = 1 ; i<=m ; i++) {
        fin >> x >> y >> z ;
        g[x].push_back({y,z}) ;
    }
    init() ;
    q.push_back(1) ;
    bellman() ;
    for(int i = 2 ; i<=n ; i++) {
        fout << d[i] << ' ' ;
    }
}