#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define oo 1<<30
#define maxN 50005

using namespace std;

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

vector < pair <int,int> > G[maxN];
queue <int> Q;
bool inQ[maxN], negC;
int n,m; int d[maxN], nrQ[maxN];

void citire()
{
    int x,y,z;
    fin>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        fin>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
    }
}

void afis()
{
    if (negC) fout<<"Ciclu negativ!";
    else
        for (int i=2; i<=n; ++i)
            fout<<d[i]<<' ';
}

void BellmanFord()
{
    for (int i=1; i<=n; ++i)
        d[i]=oo;
    d[1]=0; inQ[1]=true; ++nrQ[1]; Q.push(1);   /// 1 - Nodul de start
    while (!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        inQ[x]=false;
        for (int i=0; i<G[x].size(); ++i)
        {
            int v=G[x][i].first;
            int c=G[x][i].second;
            if (d[x] + c < d[v])
            {
                d[v]=d[x]+c;
                if (!inQ[v]) {
                    Q.push(v);
                    inQ[v]=true;
                }
                ++nrQ[v];
                if (nrQ[v]>=n)
                {
                    negC=true;
                    return;
                }
            }
        }
    }
}

int main()
{
    citire();
    BellmanFord();
    afis();
    return 0;
}