#include <iostream>
#include <fstream>
#include <deque>
#include <vector>

#define v first
#define c second
#define Infinit 2000000000

using namespace std;

vector < pair <int, int> > G[50005];
deque <int> Coada;
int N, D[50005], NStacked[50005];
bool InStack[50005], NC;

void Read ()
{
    ifstream fin ("bellmanford.in");
    int M, X, Y, Z;
    fin >> N >> M;
    for (; M>0; --M)
    {
        fin >> X >> Y >> Z;
        G[X].push_back (make_pair (Y, Z));
    }
    fin.close ();
}

void Type ()
{
    ofstream fout ("bellmanford.out");
    int i;
    if (NC==false)
    {
        for (i=2; i<=N; ++i)
        {
            fout << D[i] << " ";
        }
    }
    else
    {
        fout << "Ciclu negativ!";
    }
    fout.close ();
}

void BellmanFord (int Start)
{
    deque <int> :: iterator X;
    int V, C;
    unsigned i;
    for (i=1; i<=N; ++i)
    {
        D[i]=Infinit;
    }
    D[Start]=0;
    Coada.push_back (Start);
    InStack[Start]=true;
    NStacked[Start]++;
    while (Coada.empty ()==false)
    {
        X=Coada.begin ();
        Coada.pop_front ();
        for (i=0; i<G[*X].size (); ++i)
        {
            V=G[*X][i].v;
            C=G[*X][i].c;
            if (D[*X]+C<D[V])
            {
                D[V]=D[*X]+C;
                if (InStack[V]==false)
                {
                    Coada.push_back (V);
                    InStack[V]=true;
                    NStacked[V]++;
                    if (NStacked[V]>=N)
                    {
                        NC=true;
                        return;
                    }
                }
            }
        }
    }
}

int main()
{
    Read ();
    BellmanFord (1);
    Type ();
    return 0;
}