#include<fstream>
#include<deque>
#include<list>
#include<climits>

using namespace std;

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

const int Nmax = 50005;
const int inf = INT_MAX;

deque<int>c;

bool viz[Nmax], ciclu;
int dist[Nmax], nc, m ,n;
int fr[Nmax];

struct graph{

    int nod, cost;
};

list<graph>l[Nmax];
list<graph>::iterator it;

void read_data(){

    f >> n >> m;

    int x, y, c;

    while(f >> x >> y >> c)
        l[x].push_back({y, c});
}

void Bellman_Ford(int v){

    c.push_back(v);
    viz[v] = true;

    for(int i = 1; i <= n; i++)
        dist[i] = inf;
    dist[v] = 0;

    while(!c.empty() and !ciclu){

        nc = c.back();
        viz[nc] = false;

        if(fr[nc] >= n)
            ciclu = true;

        for(it = l[nc].begin(); it != l[nc].end(); it++)
            if(dist[it->nod] > dist[nc] + it->cost){

                dist[it->nod] = dist[nc] + it->cost;
                fr[it->nod]++;

                if(!viz[it->nod]){

                    viz[it->nod] = true;
                    c.push_front(it->nod);
                }
            }

        c.pop_back();
    }
}

void write_data(){

    for(int i = 2; i <= n; i++)
        if(dist[i] == inf)
            g << 0 << ' ';
        else
        g << dist[i] << ' ';
}

int main(){

    read_data();
    Bellman_Ford(1);
    if(ciclu)
        g << "Ciclu negativ!";
    else
    write_data();
    return 0;
}