#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

const int NMAX=50001;
const int inf=1<<31-1;

struct graf {
    int cost, node;
    struct graf *next;
};

struct graf *A[NMAX];
int dist[NMAX], poz[NMAX], h[NMAX];
int n, m, size;

void swap(int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void heapUp(int what)
{
    int f;
    while (what > 1) {
        f = what >> 1;
        if (dist[h[f]] > dist[h[what]]) {
	poz[h[f]] = what;
	poz[h[what]] = f;
	swap(f, what);
	what = f;
        }
        else
	what = 1;
    }
}

void heapDown(int what)
{
    int f;
    while (what <= size) {
        f = what;
        if ((what << 1) <= size) {
	f = what << 1;
	if (f+1 <= size)
	    if (dist[h[f+1]] < dist[h[f]])
	        ++f;
        }
        else
	return;
        if (dist[h[what]] > dist[h[f]]) {
	poz[h[what]] = f;
	poz[h[f]] = what;
	swap(what, f);
	what = f;
        }
        else
	return;
    }
}

void add(int where, int what, int cost)
{
    struct graf *q = new graf;
    q->node = what;
    q->cost = cost;
    q->next = A[where];
    A[where] = q;
}

void citire()
{
    int x, y, cost, i;
    in>>n>>m;
    for (i=1; i<=n; i++) {
        dist[i] = inf;
        poz[i] = -1;
    }

    for (i=1; i<=m; i++) {
        in>>x>>y>>cost;
        add(x, y, cost);
    }
}

void dijsktra()
{
    dist[1] = 0;
    h[++size] = 1;

    while (size) {
        int min = h[1];
        swap(1, size);
        --size;
        poz[h[1]] = 1;

        heapDown(1);
        struct graf *q = A[min];
        while (q) {
	if (dist[q->node] > dist[min] + q->cost) {
	    dist[q->node] = dist[min] + q->cost;
	    if (poz[q->node] != -1)
	        heapUp(poz[q->node]);
	    else {
	        h[++size] = q->node;
	        poz[h[size]] = size;
	        heapUp(size);
	    }
	}
	q = q->next;
        }
    }
}

int main()
{
    int i;
    citire();
    dijsktra();
    for (i=2; i<=n; ++i)
        if (dist[i]==inf) out<<"0"<<" ";
            else out<<dist[i]<<" ";
    return 0;
}