// http://infoarena.ro/problema/bellmanford
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define maxSize 50001
#define INFINITY 0x3f3f3f3f
#define location first
#define cost second

int nodes;
bool visit[maxSize];
int timesVisited[maxSize];
vector< pair<int,int> > graph[maxSize];
vector<int> dist(maxSize,INFINITY);
queue<int>  myQueue;

void read();
void write(bool status);
    bool bellmanFord(int startNode);


int main() {
    read();
    write(bellmanFord(1));

}

void read() {
    ifstream in("bellmanford.in");
    int edges,from,to,cost;

    in >> nodes >> edges;
    for(int i=1;i<=edges;i++) {
        in >> from >> to >> cost;

        graph[from].push_back(make_pair(to,cost));
    }

    in.close();
}

bool bellmanFord(int startNode) {
    dist[startNode] = 0;

    int currentNode;
    vector< pair<int,int> >::iterator neighbour,end;
    myQueue.push(startNode);    // introducem nodul de pornire in coada

    while(!myQueue.empty()) {
        // extragem primul nod
        currentNode = myQueue.front();
        // il eliminam din coada
        myQueue.pop();

        end = graph[currentNode].end();

        // toti vecinii nodului curent
        for(neighbour=graph[currentNode].begin();neighbour!=end;++neighbour)
            // daca s-a gasit un drum mai scurt
            if(dist[neighbour->location] > dist[currentNode] + neighbour->cost) {
                // ii actualizam distanta
                dist[neighbour->location] = dist[currentNode] + neighbour->cost;

                // daca nu a fost vizitat
                if(!visit[neighbour->location]) {
                    timesVisited[neighbour->location]++;

                    // ciclu negativ
                    if(timesVisited[neighbour->location] > nodes)
                        return false;
                }

                // introducem nodul in coada
                myQueue.push(neighbour->location);

                // il marcam ca vizitat
                visit[neighbour->location] = true;
            }

        // nodul curent il marcam ca nevizitat
        visit[currentNode] = false;
    }

    return true;
}

void write(bool status) {
    ofstream out("bellmanford.out");

    if(status) {
        for(int i=2;i<=nodes;i++)
            out << dist[i] << " ";
        out << "\n";
    }
    else
        out << "Ciclu negativ!\n";

    out.close();
}