#include <cstdio>
#include <bitset>
#include <queue>
#define DIM 50005
using namespace std;
const int INF = (1<<30);
struct nod
{
    int x, cost;
    nod *next;
};

nod *G[DIM];
int n, m, d[DIM], nr[DIM];


void addMuchie(const int i, const int j, const int cost)
{
    nod *p = new nod;
    p->x = j;
    p->cost = cost;
    p->next = G[i];
    G[i] = p;
}

int bell_ford()
{
    for (int i = 1; i <= n; ++i)
        d[i] = INF;

    bitset<DIM> in_queue(0);
    queue<int> Q;
    Q.push(1);
    in_queue[1] = true;
    d[1] = 0;
    int i;
    while (!Q.empty())
    {
        i = Q.front();
        Q.pop();
        in_queue[i] = false;
        if (d[i] == INF)
            continue;

        for (nod *p = G[i]; p; p = p-> next)
        {
            if (d[p->x] > d[i] + p-> cost)
            {
                d[p->x] = d[i] + p-> cost;
                if (!in_queue[p->x])
                {
                    if (nr[p->x] > n)
                        return 1;

                    Q.push(p->x);
                    in_queue[p->x] = true;
                    ++nr[p->x];
                }

            }
        }
    }
    return 0;
}

int main()
{
    FILE *f = fopen("dijkstra.in", "r");

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

    for (int x, y,c; m; --m)
    {
        fscanf(f, "%d%d%d", &x, &y, &c);
        addMuchie(x, y, c);
    }


    fclose(f);
    f = fopen("dijkstra.out", "w");
    int ciclu = bell_ford();
    if (ciclu)
        fprintf (f, "Ciclu negativ!\n");
    else
        for (int i = 2; i <= n; ++i)
            fprintf (f, "%d ", d[i]==INF?0:d[i]);

    fclose(f);
    return 0;
}