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

using namespace std;

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

class WeightedGraph{

    public:
        int to, cost;
};

const int maxV = 50000;
const int Inf = INT_MAX;

list <WeightedGraph> adjList[1 + maxV];
vector <int> dist, seen;
int V, E;

void readData(){

    fin >> V >> E;

    for(; E; --E){

        int from, to, cost;
        fin >> from >> to >> cost;

        adjList[from].push_back({to, cost});
    }
}

int main(){

    readData();

    dist.resize(1 + V);
    seen.resize(1 + V);

    fill(dist.begin(), dist.end(), Inf);
    fill(seen.begin(), seen.end(), 0);

    dist[1] = 0;

    deque <int> Queue;
    Queue.push_back(1);

    while(!Queue.empty()){

        int node = Queue.front();
        Queue.pop_front();

        ++seen[node];
        if(seen[node] == V){

            fout << "Ciclu negativ!";
            return 0;
        }

        for(const WeightedGraph &edge : adjList[node]){

            int nextNode = edge.to;
            int cost = edge.cost;

            if(dist[nextNode] > dist[node] + cost){

                dist[nextNode] = dist[node] + cost;
                Queue.push_back(nextNode);
            }
        }
    }

    for(int node = 2; node <= V; ++node)
        fout << dist[node] << ' ';
}