# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <queue>
using namespace std;

# define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0

const char *FIN = "bellmanford.in", *FOU = "bellmanford.out";
const int MAX = 50005, hg = 1 << 13, oo = 0x3f3f3f3f;

struct gr {
    int nod, cost;
    gr *next;
};

gr *G[MAX];
int N, M, poz, dp[MAX], cnt[MAX];
char ch[hg];
bool viz[MAX];

inline void cit ( int &x ) {
    int semn = 1;
    if ( ch[0] == '\0' ) fread ( ch, 1, hg, stdin ) ;
    else for ( ; (ch[poz] < '0' || ch[poz] > '9') && ch[poz] != '-' ; verf ) ;
    for ( x = 0 ; ch[poz] >= '0' && ch[poz] <= '9' || ch[poz] == '-' ; (ch[poz] == '-' ? semn = -1 : x = x * 10 + ch[poz] - '0'), verf ) ;
    x *= semn;
}

struct comp {
    bool operator () (const int &A, const int &B) {
        return dp[A] > dp[B];
    }
};

inline void baga (int x, int y, int z) {
    gr *aux = new gr;
    aux -> nod = y, aux -> cost = z;
    aux -> next = G[x];
    G[x] = aux;
}

priority_queue < int, vector <int>, comp > Q ;

void solve (void) {
    memset (dp, oo, sizeof (dp));
    for (dp[1] = 0, Q.push (viz[1] = 1); ! Q.empty (); ) {
        int act = Q.top (); viz[act] = 0; Q.pop ();
        for (gr *it = G[act]; it != NULL; it = it -> next)
            if (dp[act] + it -> cost < dp[it -> nod]) {
                dp[it -> nod] = dp[act] + it -> cost;
                if (viz[it -> nod] == 0) {
                    if (cnt[it -> nod] > N) {
                        printf ("Ciclu negativ!");
                        exit (0);
                    } else {
                        Q.push (it -> nod);
                        viz[it -> nod] = 1, ++cnt[it -> nod];
                    }
                }
            }
    }
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    cit (N), cit (M);
    for (int i = 1, x, y, z; i <= M; ++i) {
        cit (x), cit (y), cit (z);
        baga (x, y, z);
    }
    solve ();
    for (int i = 2; i <= N; ++i)
        printf ("%d ", dp[i] < oo ? dp[i] : 0);
}