#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 50001;
const int INF = 0x3f3f3f3f;

int N,M;
bool CycleisNegative = false;

vector <pair<int, int>> ADJ[NMAX];
queue<int> Q;

int dist[NMAX],NumberinQ[NMAX];
bool IsinQ[NMAX];

void bellmanford()
{

    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    Q.push(1);
    IsinQ[1] = true;


    while(!Q.empty()&&!CycleisNegative)
    {
        int x = Q.front();
        Q.pop();

        IsinQ[x] = false;
        for (auto edge : ADJ[x])
            if(dist[x] < INF)
                if(dist[x] + edge.second < dist[edge.first])
                {
                    dist[edge.first] = dist[x] + edge.second;
                    if (IsinQ[edge.first] == false)
                    {
                        if (NumberinQ[edge.first] > N)
                            CycleisNegative=true;
                        else
                        {
                            Q.push(edge.first);
                            IsinQ[edge.first] = true;
                            NumberinQ[edge.first]++;
                        }
                    }
                }

    }

}
int main()
{
    in>>N>>M;
    for(int i = 1; i<=M; i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        ADJ[x].push_back(make_pair(y,c));

    }
    bellmanford();
    if (CycleisNegative == true)
        out << "Ciclu negativ!\n";
    else
    {
        for (int i = 2; i <= N; i ++)
            out << dist[i] << " ";
    }


    return 0;
}