#include <bits/stdc++.h>

using namespace std;

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

const int nmax=5e4+10,mmax=25e4+10,inf=0x3f3f3f3f;

struct edge
{
    int u,v,cost;
};

vector<edge> edges;
int dist[nmax];
int n,m;

void read()
{
    fin>>n>>m;
    int u,v,cost;
    for(int i=1;i<=m;i++)
    {
        fin>>u>>v>>cost;
        edges.push_back({u,v,cost});
    }
}

void BellmanFord()
{
    fill(dist+1,dist+n+1,inf);
    dist[1]=0;

    for(int i=0;i<n;i++)
        for(auto it:edges)
        {
            edge currentEdge=it;

            if(dist[currentEdge.u]!=inf && dist[currentEdge.v]>dist[currentEdge.u]+currentEdge.cost)
                dist[currentEdge.v]=dist[currentEdge.u]+currentEdge.cost;
        }

    for(auto it:edges)
    {
        edge currentEdge=it;

        if(dist[currentEdge.u]!=inf && dist[currentEdge.v]>dist[currentEdge.u]+currentEdge.cost)
        {
            fout<<"Ciclu negativ!";
            return ;
        }
    }
    for(int i=2;i<=n;i++)
        fout<<dist[i]<<" ";
}

int main()
{
    read();
    BellmanFord();
    return 0;
}