#include <fstream>
#include <vector>
using namespace std;

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

struct vecin
{
    int vf, c;
};

vector<vecin> v[50001];
const long long maxi=50000001;
int viz[50001], q[50001], d[50001],m,n;

void bellmanford(int nod){
    int p,u,x,i,y,c;
    viz[nod]=1;
    p=u=1;
    q[p]=nod;
    while(p<=u){
        x=q[p++];
        viz[x] = 0;
        for (unsigned i = 0; i < v[x].size(); i++)
        {
            y = v[x][i].vf;
            c = v[x][i].c;
            if (d[x] + c < d[y])
            {
                d[y] = d[x] + c;
                if (!viz[y])
                {
                    q[++u] = y;
                    viz[y] = 1;
                }
            }
        }
    }

}

int main()
{
    int x,y,c,i;
    vecin aux;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        aux.vf = y;
        aux.c = c;
        v[x].push_back(aux);
    }
    //for(i=0;i<v[1].size();i++)
    //    d[v[1][i].vf]=v[1][i].c;
    for(i=2;i<=n;i++)
            d[i]=maxi;
    bellmanford(1);
    int s=0;
    for(i=2;i<=n;i++)
        s=s+d[i];
    if(s>0)
        for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    else
        g<<"Ciclu negativ!";
    return 0;
}