#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define MaxN 50005
#define INF 214000000
using namespace std;
 
FILE *IN,*OUT;
 
int N,M,Cnt[MaxN],X,Y,Z,v[MaxN];
vector<pair<int,int>> Graph[MaxN];
queue <int> Q;
bool Bellmanford(int node)
{
    Q.push(node);
    Cnt[node]++;
    while(!Q.empty())
    {
        if(Cnt[Q.front()]>N)
            return true;
        for(int i=0;i<Graph[Q.front()].size();i++)
        {
            if(v[Graph[Q.front()][i].first]>v[Q.front()]+Graph[Q.front()][i].second)
            {
                v[Graph[Q.front()][i].first]=v[Q.front()]+Graph[Q.front()][i].second;
                Cnt[Graph[Q.front()][i].first]++;
                Q.push(Graph[Q.front()][i].first);
            }
        }
        Q.pop();
    }
    return false;
}
int main()
{
    IN=fopen("bellmanford.in","r");
    OUT=fopen("bellmanford.out","w");
     
    fscanf(IN,"%d%d",&N,&M);
    for(int i=2;i<=N;i++)
        v[i]=INF;
    for(int i=1;i<=M;i++)
    {
        fscanf(IN,"%d%d%d",&X,&Y,&Z);
        Graph[X].push_back(make_pair(Y,Z));
    }
    if(Bellmanford(1))
        fprintf(OUT,"Ciclu negativ!");
    else for(int i=2;i<=N;i++)
        fprintf(OUT,"%d ",v[i]);
    return 0;
}