#include <fstream>
#include <vector>
#define NX 50001
#define MX 250001
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m;

struct vecin
{
    int j,c;
};

vector<vecin> v[NX];
int d[NX],q[NX];
bool viz[NX],ciclu;

void citire()
{
    int i,x,y,c;
    vecin e;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        e.j = y;
        e.c = c;
        v[x].push_back(e);
    }
}

void bellman_ford()
{
    int stanga,dreapta;
    vecin e;
    int u,i,ok;
    vector<vecin>::iterator it;

    q[1] = 1;
    stanga=dreapta=1;
    viz[1] = 1;

    while(stanga<=dreapta)
    {
        u = q[stanga];
        stanga++;
        for(it=v[u].begin(); it!=v[u].end(); it++)
        {
            e = *it;

            if(viz[e.j] == 0)
            {
                dreapta++;
                q[dreapta] = e.j;
                viz[e.j] = 1;
            }
        }
    }

    //si acum bellman-ford propriu-zis (varianta naiva)
    for(i=1; i<n; i++)
    {
        stanga=1;
        ok=1;
        while(stanga<=dreapta)
        {
            u = q[stanga];
            stanga++;
            for(it=v[u].begin(); it!=v[u].end(); it++)
            {
                e = *it;

                if(d[u]+e.c < d[e.j])
                {
                    d[e.j] = d[u]+e.c;
                    ok=0;
                }
            }
        }
        if(ok) return;
    }

    stanga=1;
    while(stanga<=dreapta)
    {
        u = q[stanga];
        stanga++;
        for(it=v[u].begin(); it!=v[u].end(); it++)
        {
            e = *it;

            if(d[u]+e.c < d[e.j])
            {
                /*d[e.j] = d[u]+e.c;
                ciclu = 1;*/
                return;
            }
        }
    }
}

int main()
{
    int i;
    citire();
    for(i=1; i<=n; i++)
    {
        d[i] = 2000000000;
    }
    d[1]=0;

    bellman_ford();

    if(ciclu) fout<<"Ciclu negativ!";
    else
    for(i=2; i<=n; i++) fout<<d[i]<<' ';

    fin.close(); fout.close();
    return 0;
}