#include <bits/stdc++.h>
#define fs first
#define sc second

using namespace std;

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

const int nmax=50005;
const int inf=1e9;

int n,m,d[nmax];
vector <pair <int,int> > gr[nmax];

bool bellyspfa(int nod)
{
    fill(d+1,d+n+1,inf);
    vector <int> cnt(n+1,0);
    vector <bool> sel(n+1,false);
    queue <int> q;

    d[nod]=0;
    q.push(nod);
    sel[nod]=true;

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

        for (auto i:gr[v])
        {
            if ( d[v]+i.sc<d[i.fs] )
            {
                d[i.fs]=d[v]+i.sc;

                if ( !sel[i.fs] )
                {
                    q.push(i.fs);
                    sel[i.fs]=true;
                    cnt[i.fs]++;

                    if ( cnt[i.fs]>n )
                        return false;  // negative cycle
                }
            }
        }
    }

    return true;
}


int main()
{
    f >> n >> m;

    for (int i=1; i<=m; i++ )
    {
        int x,y,c;
        f >> x >> y >> c;
        gr[x].push_back({y,c});
    }

    if ( bellyspfa(1)==false )
        g << "Ciclu negativ!";
    else
        for (int i=2; i<=n; i++ )
            g << d[i] << " ";
    return 0;
}