#include <bits/stdc++.h>

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
bool incoada[50005];
int ncoada[50005];
int parinte[50005];
int cost[50005];
vector <pair <int,int>> v[50005];
queue <int> Q;

int bellman_ford(int nod) {
    int nou,c;
    Q.push(nod);
    cost[nod]=0;
    incoada[nod]=1;
    ncoada[nod]=1;
    while (!Q.empty()) {
        nod = Q.front();
        Q.pop();
        incoada[nod] =0;
        for(int i=0;i<v[nod].size();i++) {
            nou = v[nod][i].first;
            c= v[nod][i].second;
            if(cost[nou]>c+cost[nod]) {
               cost[nou]=c+cost[nod];
               if(!incoada[nou]) {
                    if (ncoada[nou]>n)
                        return 0;
                    else {
                        Q.push(nou);
                        incoada[nou]=1;
                        ncoada[nou]++;
                    }
               }
            }
        }
    }
    return 1;
}

int main()
{
    int x,y,c,s;
    in>>n>>m;
    for(int i=1;i<m;i++) {
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }

    for(int i=1;i<=n;i++) {
        cost[i] = INT_MAX;
    }

    if (bellman_ford(1) == 0) {
        out<<"Ciclu negativ!\n";
        return 0;
    }
    for(int i=2;i<=n;i++) {
        out<<cost[i]<<' ';
    }

    return 0;
}