#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>
#include <tuple>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
class graf{
private:
    bool InCoada[50000];
    int n,m, vizitate[50000], distanta[50000];
public:
    graf(int n, int m);
    void bellman_ford(int s, vector <pair<int, int>>G[50000]);
};
graf::graf(int n, int m)
{
    this->n=n;
    this->m=m;
}
void graf::bellman_ford (int s, vector <pair<int, int>>G[50000]){
    queue<int>q;
    bool exista_cost_negativ = false;
    for(int i=0;i<=n;i++)
        {distanta[i]=200;
        InCoada[i]=false;
        vizitate[i]=0;}
    distanta[s]=0;
    q.push(s);
    InCoada[s] = true;
    while(q.empty() == false && exista_cost_negativ == false)
    {
        int nod_curent = q.front();
        vizitate[nod_curent]=1;
        q.pop();
        InCoada[nod_curent]=false;
        for ( size_t i = 0; i < G[nod_curent].size(); i++ )
        {
             int vecin = G[nod_curent][i].first;
             int cost = G[nod_curent][i].second;
             if(distanta[nod_curent]+cost< distanta[vecin])
             {
                 distanta[vecin]=distanta[nod_curent]+cost;
                 if(InCoada[vecin]==false)
                    {q.push(vecin);
                    InCoada[vecin]=true;}
             }
             vizitate[vecin]++;
             if(vizitate[i]>=n) //adica avem ciclu negativ,avand un nod care isi micsoreaza costul in continuare la mai mult de n-1 iteratii
             {
                 exista_cost_negativ=true;
                 break;
             }
        }
    }
    if (exista_cost_negativ==false){
        for(int i=2; i <=n;i++)
            g<<distanta[i]<<" ";
    }
    else g<<"Graful contine un ciclu negativ";
}

int main(){
    int n,m;
    bool exista_cost_negativ;
    f>>n>>m;
    int start_edge, end_edge, cost;
    vector <pair<int, int>>G[50000];
    vector<int>distanta;
    for(int i = 0; i < m; i++)
    {
        f >> start_edge >> end_edge >> cost;
        G[start_edge].push_back(make_pair(end_edge, cost));
    }
    graf g(n,m);
    g.bellman_ford(1, G);
    return 0;
}