#include <stdio.h>

#define MAX 50001
#define _INFINITY 0x3f3f3f3f

const char Infile[] = "dijkstra.in";
const char Outfile[] = "dijkstra.out";

struct node {
	   int v, cost;
	   node *next;
} *graph[MAX];

int sel[MAX], d[MAX], h[MAX], pos[MAX], n, m, hsize, source;

void ReadData();
void Add(int i, int j, int c);
void BuildHeap();
void InsertHeap(int vertex);
void MoveUp(int vertex);
void Dijkstra();
void Print();
inline int ExtractMin();
inline int LeftSon(int x);
inline int Parent(int x);

int main()
{
	freopen(Infile, "r", stdin);
    freopen(Outfile, "w", stdout);

    ReadData();
    source = 1;
    Dijkstra();
    Print();

    fclose(stdin);
    fclose(stdout);

    return 0;
}

void ReadData()
{
	int i = 0, x = 0, y = 0, c = 0;
    scanf("%d %d", &n, &m);
	for ( i = 1; i <= m; i++ )
    {
        scanf("%d %d %d", &x, &y, &c);
        Add(x, y, c);
        Add(y, x, c);
    }
}

void Add(int i, int j, int c)
{
    node *x = new node;
    x->v = j;
    x->cost = c;
    x->next = graph[i];
    graph[i] = x;
}

void BuildHeap()
{
    node *x = NULL;

    for ( int i = 1; i <= n; i++ )
        d[i] = _INFINITY;

    d[source] = 0;
    for ( x = graph[source]; x; x = x->next )
    {
        d[x->v] = x->cost;
        InsertHeap(x->v);   // insereaza un varf v
        sel[x->v] = 1;
    }
}

void InsertHeap(int vertex)
{
    int son = 0, parent = 0;

    son = ++hsize;
    parent = Parent(son);

    while ( parent && d[h[parent]] > d[h[son]] )
    {
        h[son] = h[parent];
        pos[h[son]] = son;
        son = parent;
        parent = Parent(son);
    }

    h[son] = vertex;
    pos[vertex] = son;
}

void MoveUp(int vertex)  // vertex este deja in heap
{
    int son = 0, parent = 0;

    son = pos[vertex];
    parent = Parent(son);

    while ( parent && d[h[parent]] > d[h[son]] )
    {
        h[son] = h[parent];
        pos[h[son]] = son;
        son = parent;
        parent = Parent(son);
    }

    h[son] = vertex;
    pos[vertex] = son;
}

void RebuildHeap(int i)
{
    int value = 0, son = 0, parent = 0;

    value = h[i];
    parent = i; // 1
    son = LeftSon(parent);

    while ( son <= hsize )
    {
        if ( son < hsize )
           if ( d[h[son]] > d[h[son+1]] ) son++;

        if ( d[value] > d[h[son]] )
        {
            h[parent] = h[son];
            pos[h[parent]] = parent;
            parent = son;
            son = LeftSon(son);
        }
        else break;
    }
    h[parent] = value;
    pos[value] = parent;
}

void Dijkstra()
{
    int u = 0;
    node *x = NULL;
    BuildHeap();

    while ( hsize )
    {
        u = ExtractMin(); // O(log hsize)
        sel[u] = 0;   // iese din heap
        for ( x = graph[u]; x; x = x->next )
            if ( d[x->v] > d[u] + x->cost )
            {
                d[x->v] = d[u] + x->cost;
                if ( sel[x->v] )     // este in Heap
                    MoveUp(x->v);    // urca de unde se gasea
                else                 // nu este
                {
                    InsertHeap(x->v);//
                    sel[x->v] = 1;
                }
            }
    }
}

void Print()
{
    for ( int i = 2; i <= n; i++ )
        printf("%d ", d[i]);
}

int ExtractMin()
{
    int min = h[1];
    h[1] = h[hsize--];
    RebuildHeap(1);

    return min;
}

inline int LeftSon(int x)
{
    return 2 * x;
}

inline int Parent(int x)
{
    return x / 2;
}