#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
#include <list>
#include <algorithm>
 
#define Nmax 50005
#define inf 1000000000
 
using namespace std;
 
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
 
int N, M;
vector <pair<int,int> >graf_ponderat[Nmax];
queue <int> q;
bool verif_q[Nmax];

int D[Nmax]; // D[i] – distanta minima intre nodul de start si nodul numarul i
int viz[Nmax];
 
class Graf{
private:
    int Nr_Noduri, Nr_Muchii;
    vector<int> GRAF[Nmax]; // lista de adiacenta
    // pair< int, pair<int,int> > graf_ponderat[400010];   // lista de adiacenta pentru graf ponderat
 
public:
    Graf(int N, int M); // constructor
    void Citire_BellmanFord();
    bool BellmanFord( int nod );
    void Afisare_BellmanFord();
};
 
// constructor
Graf :: Graf(int N, int M)
{
    Nr_Noduri = N;
    Nr_Muchii = M;
}
 
void Graf :: Citire_BellmanFord()
{
    for ( int i = 1; i <= Nr_Muchii; i++ )
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        graf_ponderat[x].push_back(make_pair(y, cost));
    }
 
    // initializari
    for ( int i = 1; i <= Nr_Noduri; i++ )
    {
        viz[i] = 0;
        D[i] = inf;
        verif_q[i] = 0;
    }  
}
 
bool Graf :: BellmanFord(int nodStart)
{   
    // distanta pana la nodul de start = 0
    D[nodStart] = 0;
 
    // Punem nodul de start in coada
    q.push(nodStart);
    verif_q[nodStart] = 1;
 
    while ( !q.empty() )
    {
        // extragem nodul curent
        int nod = q.front();
        q.pop();
        viz[nod]++;
        if ( viz[nod] >= Nr_Noduri )
            return 0;
        
        verif_q[nod] = 0;
        for ( size_t i = 0; i < graf_ponderat[nod].size(); i++ )
        {
            int vecin = graf_ponderat[nod][i].first;
            int cost = graf_ponderat[nod][i].second;
            // daca gasim o distanta mai mica
            if ( D[nod] + cost < D[vecin] )
            {
                D[vecin] = D[nod] + cost;
                // daca vecinul nu se afla in coada il adaugam
                if ( ! verif_q[vecin] )
                    q.push(vecin);
                
            }
        }
    }
    return 1;
}
 
void Graf :: Afisare_BellmanFord()
{
    if ( BellmanFord(1) )
    {
        for ( int i = 2; i <= Nr_Noduri; i++ )
            fout << D[i] << " ";
    }
    else
        fout << "Ciclu negativ!";
}
 
int main()
{
    fin >> N >> M;
    Graf G(N, M);
    G.Citire_BellmanFord();
    G.Afisare_BellmanFord();
    
    return 0;
}