#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];
int best[NMAX];
vector <nod> :: iterator j;

struct comp {

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

        return best[a] > best[b];

    }

};

priority_queue <int, vector <int>, 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 (1);
    while (!q.empty ()) {
        k = q.top ();
        q.pop ();
        for (j = G[k].begin (); j != G[k].end (); ++j)
            if (best[j->f] > best[k] + j->c)
                best[j->f] = best[k] + j->c,
                q.push (j->f);

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

}