#include <iostream>
#include <fstream>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

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

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;
        //cout<<v<<" "<<u<<endl;
        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(node_with_cost,1);
    return 0;
}