#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdlib>
#define nod first
#define cost second
using namespace std;

const int NMAX = 50003, INFI = 2e9;

vector <pair<int, int> > G[NMAX];
queue <int> Q;
int best_cost[NMAX], times_in_queue[NMAX];

int main () {

    freopen ("bellmanford.in", "r", stdin);
    freopen ("bellmanford.out", "w", stdout);
    int N, M, a, b, c, i;
    vector <pair <int, int> > :: iterator j;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i)
        scanf ("%d%d%d", &a, &b, &c),
        G[a].push_back (make_pair (b, c));
    for (i = 2; i <= N; ++i)
        best_cost[i] = INFI;
    Q.push (1);
    times_in_queue[1] = 1;
    while (!Q.empty ()) {
        i = Q.front ();
        Q.pop ();
        for (j = G[i].begin (); j != G[i].end (); ++j)
            if (best_cost [j->nod] > best_cost[i] + j->cost) {
                best_cost [j->nod] = best_cost[i] + j->cost,
                Q.push (j->nod),
                ++times_in_queue[j->nod];
                if (times_in_queue[j->nod] > N)
                    printf ("Ciclu negativ!"),
                    exit (EXIT_SUCCESS);
            }

    }
    for (i = 2; i <= N; ++i)
        printf ("%d ", best_cost[i]);

}