#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#define c first
#define f second
using namespace std;

typedef pair <int, int> nod;
const int NMAX = 50003, INFI = 2e9;
vector <nod> G[NMAX];
bitset <NMAX> viz;
int best[NMAX];
vector <nod> :: iterator j;

struct comp {

    bool operator ()(const nod &a, const nod &b) {

        return a > b;

    }

};

priority_queue <nod, vector <nod>, comp> q;


int main () {

    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);
    int N, M, i, a, b, c, k;
    scanf ("%d%d", &N, &M);
    for (i = 2; i <= N; ++i)
        best[i] = INFI;
    for (i = 1; i <= M; ++i)
        scanf ("%d%d%d", &a, &b, &c),
        G[a].push_back (make_pair (c, b));
    q.push (make_pair (0, 1));
    while (!q.empty ()) {
        k = q.top ().f;
        q.pop ();
        for (j = G[k].begin (); j != G[k].end (); ++j)
            if (!viz [j->f] && best[j->f] > best[k] + j->c)
                best[j->f] = best[k] + j->c,
                q.push (make_pair (best[j->f], j->f));
        viz[k] = 1;

    }
    for (i = 2; i <= N; ++i)
        printf ("%d ", best[i] == INFI ? 0 : best[i]);

}