#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define ll long long
#define pb push_back
#define pf push_front
#define nmax 1000
#define inf 2e9
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int N,M;
vector<pair<int,int> > adj[50005];
bool viz[50005];
int dist[50005];
int freq[50005];
bool Bellmanford(int nod)
{
    queue<int> q;
    q.push(nod);
    viz[nod]=1;
    dist[nod]=0;
    while(!q.empty())
    {
        int node=q.front();
        freq[node]++;
        if(freq[node]>=N)
        {
            return 0;
        }
        q.pop();
        viz[node]=0;
        for(auto x:adj[node])
        {
            if(dist[x.first]>dist[node]+x.second)
            {
                dist[x.first]=dist[node]+x.second;
                if(viz[x.first]==0)
                {
                    viz[x.first]=1;
                    q.push(x.first);
                }

            }
        }

    }
    return 1;
}
int main()
{
   f>>N>>M;
   for(int i=1;i<=M;i++)
   {
       int x,y,c;
       f>>x>>y>>c;
       adj[x].pb({y,c});
   }
   for(int i=1;i<=N;i++) dist[i]=2e9;
   if(Bellmanford(1))
   {
       for(int i=2;i<=N;i++)
       {
           g<<dist[i]<<" ";
       }
   }
   else
   {
       g<<"Ciclu negativ!"<<'\n';
   }




}