#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int,int> > adj[50002];
int n,m;
int cost[50002];
bool inqueue[50002];
int aparitii[50002];
bool negative_cycle=0;
void bellman(int s)
{
    queue<int> q;
    inqueue[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        aparitii[v]++;
        if(aparitii[v]==n)
        {
            negative_cycle=1;
            return;
        }
        inqueue[v]=0;
    //    int ok=0;
        for(size_t i=0;i<adj[v].size();i++)
        {
            int u=adj[v][i].first,w=adj[v][i].second;
            if(cost[v]+w<cost[u])
            {
            //    ok=1;
                cost[u]=cost[v]+w;
                if(inqueue[u]==0)
                {
                    q.push(u);
                    inqueue[u]=1;
                }
            }
        }
    }
}


int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int v1,v2,w;
        fin>>v1>>v2>>w;
        adj[v1].push_back({v2,w});
    }
    for(int i=2;i<=n;i++)
    {
        cost[i]=0x3f3f3f3f;
    }
    bellman(1);
    if(negative_cycle)
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<<cost[i]<<' ';
    return 0;
}