#include <fstream>
using namespace std;

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

const int maxn = 50001;
int n,m,k;
int heap[maxn],d[maxn],poz[maxn];

struct Nod{
    int value,cost;
    Nod*next;
}*graph[maxn],*q;

void AddToGraph(int from,int to, int ccost)
{
    q = new Nod;
    q->value = to;
    q->cost = ccost;
    q->next = graph[from];
    graph[from] = q;
}

void Read()
{
    int i,a1,a2,a3;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a1>>a2>>a3;
        AddToGraph(a1,a2,a3);
    }
}

void SwapValues(int x[maxn],int a1,int a2)
{
    int aux = x[a1];
    x[a1] = x[a2];
    x[a2] = aux;
}



void HeapSift(int w)
{
    int son = 0;
    do{
        son = 0;
        if(2*w <= k)
        {
            son = 2*w;
            if(2*w+1 <= k && d[heap[2*w]] > d[heap[2*w+1]])
                son = 2*w+1;
            if(d[heap[w]] < d[heap[son]])
                son = 0;
        }
        if(son)
        {
            SwapValues(poz,heap[w],heap[son]);
            SwapValues(heap,w,son);
        }
    }while(son);
}

void HeapPercolate(int w)
{
    int key = heap[w];

    while(w>1 && d[heap[w]] > d[heap[w/2]] )
    {
        heap[w] = heap[w/2];
        SwapValues(poz,heap[w],heap[w/2]);
        w/=2;
    }

    heap[w] = key;
}

void DeleteTheFirst()
{
    SwapValues(heap,1,k);
    HeapPercolate(1);
    k--;
}

void Dijkstra()
{
    heap[++k] = 1;

    while(k >= 1)
    {
        int acum = heap[1];
        DeleteTheFirst();

        q = graph[acum];
        while(q)
        {
            if(!d[q->value] || d[q->value] > d[acum] + q->cost)
            {
                d[q->value] = d[acum] + q->cost;

                if(!poz[q->value])
                {
                    heap[++k] = q->value;
                    HeapSift(k);
                }
                else
                    HeapPercolate(poz[q->value]);
            }
            q=q->next;
        }
    }
}

void Write()
{
    for(int i=2;i<=n;i++)
        g<<d[i]<<' ';
}

int main()
{
    Read();
    Dijkstra();
    Write();
    return 0;
}