#include <iostream>
#include <fstream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define Nmax 50005
#define inf 100009
int n,m;


void bellmanford_optimizat(vector< pair<int,int> > node_with_cost[Nmax],int source)
{
    vector<int> dist(n+1,inf);
    queue<int> q;
    vector<int> cnt(n+1,0);
    vector<bool> inqueue(n+1,false);

    dist[source]=0;
    q.push(source);
    inqueue[source]=true;

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        inqueue[u] = false;

        for(auto neighbour:node_with_cost[u])
        {
            int v = neighbour.first;
            int weight = neighbour.second;

            if(dist[u]+weight<dist[v]){
                dist[v] = dist[u]+weight;
                if(!inqueue[v])
                {
                    q.push(v);
                    inqueue[v] = true;
                    cnt[v]++;
                    if(cnt[v]>n)
                        {
                            g<<"Ciclu negativ!";
                            return;
                        }
                }
            }

        }
    }
        for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";
}

void bellmanford(vector< pair<int,int> > node_with_cost[Nmax],int source)
{
    vector<int> dist(n+1,inf);
    dist[source]=0;

    for(int k=1;k<=n-1;k++)
        for(int i=1;i<=n;i++)
        for(auto neighbour:node_with_cost[i])
    {
        int u = neighbour.first;
        int v = i;
        int weight = neighbour.second;
        dist[u]=min(dist[u],dist[v]+weight);
    }
    for(int i=1;i<=n;i++)
        for(auto neighbour:node_with_cost[i])
    {
        int u = neighbour.first;
        int v = i;
        int weight = neighbour.second;
        if(dist[v]+weight<dist[u])
         {
                g<<"Ciclu negativ!";
                return;
         }

    }

    for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";
}


int main()
{
    vector< pair<int,int> > node_with_cost[Nmax];
    f>>n>>m;

    for(int i=0;i<m;i++)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        node_with_cost[x].push_back(make_pair(y,cost));

    }
    bellmanford_optimizat(node_with_cost,1);
    return 0;
}