#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#include <algorithm>

using namespace std;

const int Nmax = 50005;
const int Mmax = 250005;
const int INF = 1005;

struct muchie{
    int start, finish, cost, poz;
};

struct nod{
    int dist;
    vector<muchie> muchie_start;
};

int n, m;
nod nodes[Nmax];
muchie muchii[Mmax];
queue<int> q;
int vizitat[Nmax];
bitset<Nmax> inQueue;

bool cmp(muchie a, muchie b){
    if(a.start == b.start){
        return a.finish < b.finish;
    }
    return a.start < b.start;
}

void precalc_distante(){
    nodes[1].dist = 0;
    for(int i = 2; i <= n; i++){
        nodes[i].dist = INF;
    }
}

bool spfa(){
    int poz;

    precalc_distante();

    inQueue[1] = 1;
    vizitat[1]++;
    q.push(1);

    while(!q.empty()){
        poz = q.front();

        inQueue[poz] = 0;
        q.pop();

        for(muchie adiacent : nodes[poz].muchie_start){
            if(nodes[adiacent.start].dist + adiacent.cost < nodes[adiacent.finish].dist){
                nodes[adiacent.finish].dist = nodes[adiacent.start].dist + adiacent.cost;

                if(!inQueue[adiacent.finish]){
                    q.push(adiacent.finish);
                    inQueue[adiacent.finish] = 1;
                    vizitat[adiacent.finish]++;

                    if(vizitat[adiacent.finish] > n){
                        return 0;
                    }
                }
            }
        }
    }

    return 1;
}

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

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> muchii[i].start >> muchii[i].finish >> muchii[i].cost;
        nodes[muchii[i].start].muchie_start.push_back(muchii[i]);
    }

    if(!spfa()){
        fout << "Ciclu negativ!";
    }
    else{
        for(int i = 2; i <= n; i++){
            fout << nodes[i].dist << " ";
        }
    }

    return 0;
}