// infoarena: problema/bellmanford //
#include <fstream>
#include <vector>
using namespace std;

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

const int MAXN = 50010;
const int MAXM = 250010;

struct MUCHIE
{
    int s,e,l,d;
    MUCHIE(int _s, int _e, int _l, int _d)
    {
        s = _s;
        e = _e;
        l = _l;
        d = _d;
    }
};

vector<int> g[MAXN];
int i,j,n,m,x,y,z,pred[MAXN],s[MAXM],e[MAXM],l[MAXM],d[MAXN];

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

    for(i=1; i<=m; i++)
    {
        in>>x>>y>>z;
        g[x].push_back(i);
        s[i] = x;
        e[i] = y;
        l[i] = z;
    }

    for(i=2; i<=n; i++)
        d[i] = 1<<29;

    for(i=2; i<=n; i++)
        for(j=1; j<=m; j++)
            if(l[j] + d[s[j]] < d[e[j]])
            {
                d[e[j]] = l[j] + d[s[j]];
                pred[e[j]] = s[j];
            }

    for(i=1; i<=m; i++)
        if(l[i] + d[s[i]] < d[e[i]])
        {
            out<<"Ciclu negativ!";
            return 0;
        }

    for(i=2; i<=n; i++)
        out<<d[i]<<' ';

    return 0;
}