#include <bitset>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

FILE* fin = fopen ("dijkstra.in", "r");
FILE* fout = fopen ("dijkstra.out", "w");

const int bufSize = 8192;
char buf[bufSize];
int ptr = bufSize - 1;

inline int getInt ()
{
    while (buf[ptr] < '0' || '9' < buf[ptr]) {
        if (++ptr >= bufSize) {
            fread (buf, bufSize, 1, fin), ptr = 0;
        }
    }
    int nr = 0;
    while ('0' <= buf[ptr] && buf[ptr] <= '9') {
        nr = nr * 10 + buf[ptr] - '0';
        if (++ptr >= bufSize) {
            fread (buf, bufSize, 1, fin), ptr = 0;
        }
    }
    return nr;
}

#define MAXN 50010
#define INF 0x3f3f3f3f

vector <pair <int, int> > g[MAXN];
typedef vector <pair <int, int> >::iterator iter;

int n, m, d[MAXN];

struct comp {
    bool operator () (int a, int b)
    {
        return d[a] > d[b];
    }
};


void dijkstra (int source)
{
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
    }

    bitset <MAXN> viz;
    priority_queue <int, vector <int>, comp> q;

    d[source] = 0, viz[source] = true;
    q.push (source);

    while (!q.empty ()) {
        int nd = q.top ();
        q.pop ();

        for (iter it = g[nd].begin (); it < g[nd].end (); ++it) {
            if (d[it->first] <= d[nd] + it->second)
                continue;

            d[it->first] = d[nd] + it->second;
            if (!viz[it->first]) {
                q.push (it->first);
                viz[it->first] = true;
            }
        }
        viz[nd] = false;
    }
}

int main ()
{
    n = getInt (), m = getInt ();

    for (int i = 1, x, y, c; i <= m; ++i) {
        x = getInt (), y = getInt (), c = getInt ();

        g[x].push_back (make_pair (y, c));
    }

    dijkstra (1);

    for (int i = 2; i <= n; ++i) {
        fprintf (fout, "%d ", d[i] == INF ? 0 : d[i]);
    }

    fclose (fin);
    fclose (fout);
    return 0;
}