#include <cstdio>
#include <vector>
#include <deque>
#include <bitset>

#define DIM 51000
#define INF 51000000

#define value first
#define cost second
using namespace std;

int nrNodes, nrEdges, node1, node2, cost;
bitset <DIM> Marked; deque <int> Deque;
vector <pair <int, int> > Edges[DIM];
int D[DIM], Count[DIM];

bool bellmanFord (int startNode)
{
    Deque.push_back(startNode);
    Count[startNode] ++;
    Marked[startNode] = 1;

    while (!Deque.empty())
    {
        vector <pair <int, int> > :: iterator it;
        for (it = Edges[Deque.front()].begin(); it != Edges[Deque.front()].end(); it++)
        {
            pair <int, int> nextNode = *it;

            if (D[nextNode.value] > D[Deque.front()] + nextNode.cost)
            {
                D[nextNode.value] = D[Deque.front()] + nextNode.cost;

                if (!Marked[nextNode.value])
                {
                    Deque.push_back(nextNode.value);
                    Marked[nextNode.value] = 1;
                    Count[nextNode.value] ++;

                    if (Count[nextNode.value] == nrNodes)
                        return 0;
                }
            }
        }
        Marked[Deque.front()] = 0;
        Deque.pop_front();
    }

    return 1;
}

int main ()
{
    freopen ("dijkstra.in" ,"r", stdin );
    freopen ("dijkstra.out","w", stdout);

    scanf ("%d %d", &nrNodes, &nrEdges);
    for (int i = 1; i <= nrEdges; i ++)
    {
        scanf ("%d %d %d", &node1, &node2, &cost);
        Edges[node1].push_back (make_pair(node2, cost));
    }

    for (int i = 2; i <= nrNodes; i ++)
        D[i] = INF;

    int ok = bellmanFord (1);

    if (!ok) printf ("Ciclu negativ!");
    else {
        for (int i = 2; i <= nrNodes; i ++)
            printf ("%d ", D[i]);
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}