#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <set>
using namespace std;

#define min(a, b) (((a) < (b)) ? (a) : (b))

#define INF 0x3f3f3f3f
#define MAXN 50010

int n, m, dist[MAXN];

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

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

    dest[source] = 0;

    bitset <MAXN> viz;
    set<pair<int, int> > q;

    for (int i = 1; i <= n; ++i) {
        q.insert (make_pair (dest[i], i));
    }

    for (int i = 1; i < n; ++i) {
        int nd = q.begin ()->second;
        q.erase (q.begin ());

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

                q.insert (make_pair (dest[it->first], it->first));
            }
        }
    }
}

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

    fscanf (fin, "%d %d\n", &n, &m);

    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        fscanf (fin, "%d %d %d\n", &x, &y, &z);

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

    dijkstra (1, dist);

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

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