#include <cstdio>
#include <queue>
#include <vector>

#define x first
#define y second
#define dmax 50001
#define inf 199999999
#define mp make_pair
#define pb push_back

using namespace std;

FILE *f=fopen("bellmanford.in", "r");
FILE *g=fopen("bellmanford.out", "w");

int use[dmax], useq[dmax], m, n, d[dmax];
typedef pair<int, int> pi;
vector <pi> v[dmax];

queue <int> q;


void read()
{
    int a, b,c;
    fscanf(f, "%i %i", &n, &m);
    for(int i=1; i<=m; i++)
    {
        fscanf(f, "%i %i %i ", &a, &b, &c);
        v[a].pb(mp(b,c));
        //v[b].pb(mp(a,c));
    }

}

bool bellmanford()
{
    for(int i=1; i<=n; i++) d[i]=inf;

    q.push(1);
    useq[1]=1;
    d[1]=0;

    while(!q.empty())
    {
        int k=q.front();
        q.pop(); useq[k]=0;

        for(int ii=0; ii<v[k].size(); ii++)
        {
            pi a=v[k][ii];

            if(a.y+d[k]<d[a.x])
            {
                d[a.x]=d[k]+a.y;
                use[a.x]++;
                if(use[a.x]==n)
                    return false;
                if(!useq[a.x])
                {
                    q.push(a.x);
                    useq[a.x]=1;
                }
            }

        }
    }
    return true;

}



int main()
{

    read();
    if(bellmanford())
        for(int i=2;i<=n;i++)
    fprintf(g, "%i ", d[i]);
    else fprintf(g, "Ciclu negativ!");
    fprintf(g, "\n");

    return 0;
}