#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 100010
#define oo (1<<30)
#define vecin first
#define cost second

int N,M;

int Dist[NMAX];
int NrInQueue[NMAX];

bool NegativeCycle;

bool InQueue[NMAX];

vector < pair < int , int > > G[NMAX];

queue < int > BF;

void Read()
{
    freopen("bellmanford.in","r",stdin);

    scanf("%d%d",&N,&M);
    for(int i=1,x,y,z;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(make_pair(y,z));
    }
}

void BellmanFord(int StartNode)
{
    for(int i=1;i<=N;i++)
        Dist[i]=oo;

    BF.push(StartNode);
    Dist[StartNode] = 0;

    while(!BF.empty())
    {
        int node = BF.front();
        BF.pop();
        InQueue[node] = false;

        for(vector < pair < int , int > >  :: iterator it = G[node].begin(); it != G[node].end(); ++ it)
            if(Dist[node] + (*it).cost < Dist[(*it).vecin])
            {
                Dist[(*it).vecin] = Dist[node] + (*it).cost;

                if(!InQueue[(*it).vecin])
                {
                    BF.push((*it).vecin);
                    InQueue[(*it).vecin] = true;
                    NrInQueue[(*it).vecin] ++;

                    if(NrInQueue[(*it).vecin] >= N)
                    {
                        NegativeCycle = true;
                        return;
                    }
                }
            }
    }
}

void Print()
{
    freopen("bellmanford.out","w",stdout);

    if(NegativeCycle)
        printf("Ciclu negativ!");
    else
        for(int i=2;i<=N;i++)
            printf("%d ",Dist[i]);
}

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