#include <fstream>
#include <queue>
#include <vector>
#define pb push_back
#define mk make_pair
#define INF 0x3f3f3f3f
using namespace std;

const int Dim = 50001;

vector < pair<int,int> > G[Dim];
queue < int > Q;
int N,M,D[Dim],T[Dim];
bool Valid,V[Dim];

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

void Read()
{
    fin >> N >> M;

    int A,B,C;

    for (int i = 1;i <= M;i++)
    {
        fin >> A >> B >> C;
        G[A].pb(mk(B,C));
    }
}

void BellmanFord()
{
    Valid = true;
    int Node,X,Y;

    for (int i = 2;i <= N;i++)
        D[i] = INF;

    D[1] = 0;
    Q.push(1);
    V[1] = true;

    while (!Q.empty())
    {
        Node = Q.front();
        Q.pop();
        V[Node] = false;

        for (int i = 0;i < G[Node].size();i++)
        {
            X = G[Node][i].first;
            Y = G[Node][i].second;

            if (D[Node] < INF)
            if (D[Node] + Y < D[X])
            {
                D[X] = D[Node] + Y;

                if (!V[X])
                {
                    if (T[X] > N)
                    {
                        Valid = false;
                        return;
                    }
                    Q.push(X);
                    V[X] = true;
                    T[X]++;
                }
            }
        }
    }
}

int main()
{
    Read();
    BellmanFord();
    if (Valid)
    {
        for (int i = 2;i <= N;i++)
            fout << D[i] << " ";
    }
   else
            fout << "Ciclu negativ!";

   return 0;
}