#include <fstream>
#define inf 1000*250000+1
#include <deque>
#include <bitset>
#include <vector>

using namespace std;

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

int n, m, i, a, b, c, nr[50002], d[50003];
bitset<50003> in;
vector<pair<int, int> > v[50002];
deque<int> q;

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[a].push_back({b, c});
    }
    d[1] = 0, nr[1] = 1;
    for(i=2;i<=n;i++)
        d[i] = inf, nr[i] = in[i] = 0;
    q.push_back(1);
    in[1] = 2;
    while(!q.empty()){
        int p = q[0];
        q.pop_front();
        in[p] = 0;
        for(i = 0;i<v[p].size();i++){
            int vecin = v[p][i].first;
            int dist = v[p][i].second;
            if(d[vecin] > dist+d[p]){
                d[vecin] = dist + d[p];
                nr[vecin]++;
                if(nr[vecin] == n-1){
                    fout<<"Ciclu negativ!";
                    return 0;
                }
                if(in[vecin] == 0)
                    in[vecin] = 1, q.push_back(vecin);
            }
        }
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}