#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int maxN = 50001;
const int infinity = 2000000000;
int N, M;

struct neighbor{
    int node;
    int cost;
    neighbor *next;
} *G[maxN];

int dist[maxN];
bool visited[maxN];
int heap[maxN], heap_size = 0;
int poz[maxN];

void swap_heap_positions(int x, int y) {
    poz[heap[x]] = y;
    poz[heap[y]] = x;
    int swap_ = heap[x];
    heap[x] = heap[y];
    heap[y] = swap_;
}

void up_heap_position(int x) {
    while(x > 1 && dist[heap[x]] < dist[heap[x >> 1]])
    {
        swap_heap_positions(x, x >> 1);
        x = x >> 1;
    }
}

void down_heap_position(int x) {
    while(x) {
        if( (x << 1) > heap_size)
            return;

        int min_son = x << 1;
        if( (x << 1) + 1 <= heap_size &&
        dist[heap[ (x << 1) + 1]] < dist[heap[min_son]])
            min_son = (x << 1) + 1;
        if(dist[heap[x]] > dist[heap[min_son]]) {
            swap_heap_positions(x, min_son);
            x = min_son;
        }
        else x = 0;
    }

}

int extractMinNode()
{
    if(!heap_size)
        return 0;

    swap_heap_positions(1, heap_size);
    heap_size--;
    down_heap_position(1);
    return heap[heap_size + 1];
}

void dijkstra()
{
    heap[++heap_size] = 1;
    poz[1] = 1;
    for(int current = 1; current != 0; current = extractMinNode())
    {
        visited[current] = true;
        for(neighbor *p = G[current]; p != NULL; p = p->next)
        {
            if(!visited[p->node])
            {
                int altDistance = dist[current] + p->cost;
                if(dist[p->node] == infinity) {
                    dist[p->node] = altDistance;
                    heap[++heap_size] = p->node;
                    up_heap_position(heap_size);
                }
                else if(altDistance < dist[p->node]) {
                    dist[p->node] = altDistance;
                    up_heap_position(poz[p->node]);
                }
            }
        }
    }
}

int main()
{
    fin >> N >> M;
    for(; M; M--) {
        int A, B, C;
        fin >> A >> B >> C;
        neighbor *p = new neighbor;
        p->node = B;
        p->cost = C;
        p->next = G[A];
        G[A] = p;
    }

    dist[1] = 0;
    for(int i=2; i<=N; i++)
        dist[i] = infinity;

    dijkstra();
    for(int i=2; i<=N; i++) {
        if(dist[i] == infinity)
            fout << 0 << ' ';
        else
            fout << dist[i] << ' ';
    }

    fout << '\n';

	fin.close();
	fout.close();
	return 0;
}