#include <bits/stdc++.h>
#define N 50007
using namespace std;

ifstream fin("bellmanford.in");ofstream fout("bellmanford.out");

int n,m;
vector<pair<int,int>>g[N];
void BelmanFord(int start)
{
    vector<int> dist(N,250000009);
    vector<int> ct(N,0);
    dist[start]=0;
    queue<int> q;
    q.push(start);
    /// daca un nod nu a fost optimizat atunci nu are rost sa mai optimizam din el
    while( !q.empty() )
    {
        int x=q.front();
        q.pop();
//        cout << x <<"  ";
        for(auto w:g[x])
        {
            int y=w.second;
            int c=w.first;

            if( dist[y]>dist[x]+c )
            {
                q.push(y);
                ct[y]++;
                if( ct[y]==n )
                {
                    fout << "Ciclu negativ!\n";
                    /// un drum minim trece prin maxim n-1 noduri
                    /// daca il updatam de n ori nu e bn...
                    return ;
                }
                dist[y]=dist[x]+c;
            }
        }

    }

    if( 0 )
        ;
    else
        for(int i=1;i<=n;i++)
            if( i!=start )
                fout << dist[i] << " ";
}

int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        g[x].push_back({c,y});
    }
    BelmanFord(1);
    fin.close();fout.close();
    return 0;
}