#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define inf 999999999
#define f first
#define s second
#define mp make_pair
int N,M,viz[50003],dist[50003],ok;
class maimic
{
public:
    bool operator()(int n1,int n2)
    {
        return dist[n1]>dist[n2];
    }
};
priority_queue<int,vector<int>,maimic>heap;
vector<pair<int,int> >v[50003];

void Bellman_Ford(int xp)
{
    int u,y,c;
    for(int i = 1 ; i <= N ; i++)
        dist[i] = inf;
    viz[xp] = 1;
    dist[xp] = 0;
    heap.push(xp);

    while( !heap.empty() )
    {
        u = heap.top();
        heap.pop();

        for(int k = 0 ; k < v[u].size() ; k++)
        {
            y = v[u][k].f;
            c = v[u][k].s;
            if( dist[y] > dist[u] + c )
            {
                dist[y] = dist[u] + c;
                viz[y]++;
                if( viz[y] == N )
                    ok = 1;
                else
                    heap.push(y);
            }
        }
        if( ok == 1 )
           break;
    }

    if( ok == 1 )
        fout<<"Ciclu negativ!";
    else
        for(int i = 1 ; i <= N ; i++)
            if( i != xp )
               fout<<dist[i]<<' ';
}

int main()
{
    int a,b,c;
    fin>>N>>M;
    for(int i = 1 ; i <= M ; i++)
    {
        fin>>a>>b>>c;
        v[a].push_back(mp(b,c));
    }
    Bellman_Ford(1);
    return 0;
    for(int i = 1 ; i <= N ; i++)
    {cout<<"lista lui "<<i<<" : ";
    for(int k = 0 ; k < v[i].size() ; k++)
        cout<<v[i][k].f<<"->"<<v[i][k].s<<' ';
     cout<<'\n';
    }
}