#include <cstdio>

#define sqrInf 999999999

using namespace std;

FILE *f, *g;

int n, m;

int c[1000001];

int k;

int lst[50001];
int cntQue[50001];
int dist[50001];
bool inQue[50001];

int neg;

int cost[250001];
int urm[250001];
int nod[250001];

void add(int a, int b, int c)
{
    k ++;

    urm[k] = lst[a];
    nod[k] = b;
    cost[k] = c;

    lst[a] = k;
}

void readFile()
{
    f = fopen("bellmanford.in", "r");

    fscanf(f, "%d%d", &n, &m);

    int i;
    int a, b, c;
    for(i = 1; i <= m; i ++)
    {
        fscanf(f, "%d%d%d", &a, &b, &c);

        add(a, b, c);
    }

    for(i = 1; i <= n; i ++)
        dist[i] = sqrInf;

    fclose(f);
}

void solve()
{
    int st = 1, dr = 0;
    int p;

    dist[1] = 0;

    c[++ dr] = 1;

    inQue[1] = 1;

    int x;

    while(st <= dr && neg == 0)
    {
        x = c[st ++];

        inQue[x] = 0;

        for(p = lst[x]; p != 0; p = urm[p])
        {
            if(dist[nod[p]] > dist[x] + cost[p])
            {
                dist[nod[p]] = dist[x] + cost[p];

                if(inQue[nod[p]] == 0)
                {
                    if(cntQue[nod[p]] > n)
                        neg = 1;

                    else
                    {
                        c[++ dr] = nod[p];

                        inQue[nod[p]] = 1;

                        cntQue[nod[p]] ++;
                    }
                }
            }
        }
    }
}

void printFile()
{
    g = fopen("bellmanford.out", "w");

    if(neg == 1)
        fprintf(g, "Ciclu negativ!\n");

    else
    {
        int i;
        for(i = 2; i <= n; i ++)
            fprintf(g, "%d ", dist[i]);

        fprintf(g, "\n");
    }

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}