#include <bits/stdc++.h>

std::ifstream in("bellmanford.in");
std::ofstream out("bellmanford.out");

using namespace std;

const int MAX = 50005;

vector < pair < int , int > > myVector[MAX];
int CNT[MAX];
bitset < MAX > beenThere;
int D[MAX];
bool negative;
int N,M;
queue < int > myQueue;

inline void scanDATA()
{

    in >> N >> M;
    for ( int i = 2 ; i <= N ; ++i)
        D[i] = ( 1 << 30);
    for ( int i = 1 ; i <= M ; ++i)
    {
        int x,y,price;
        in >> x >> y >> price;
        myVector[x].push_back(make_pair(y,price));
    }
}

void BellMan()
{
    D[1] = 0;
    beenThere[1] = true;
    myQueue.push(1);
    while(!myQueue.empty())
    {
        int currentNode = myQueue.front();
        myQueue.pop();
        beenThere[currentNode] = false;
        for( auto x : myVector[currentNode])
        {
            if(D[x.first] > D[currentNode] + x.second)
            {
                D[x.first] = D[currentNode] +x.second;
                if(!beenThere[x.first])
                {
                    if(CNT[x.first] > N)
                        negative = true ;
                    else
                    {
                        beenThere[x.first] = true;
                        CNT[x.first]++;
                        myQueue.push(x.first);
                    }
                }
            }
        }
    }
}

int main()
{
    scanDATA();
    BellMan();
    if(!negative)
        for ( int i = 2 ; i <= N ; ++i)
        out << D[i] <<" ";
    else out << "Ciclu negativ!";

}