#include "cstdio"
#include "fstream"
#include "vector"
#define fin "dijkstra.in"
#define fout "dijkstra.out"
#define inf 0x3f3f3f3f
#define nMax 50010

using namespace std;

    int heap[2*nMax],dpt,viz[nMax];

    typedef struct drum { int x,c; };
    int n,m,first,d[nMax];
    vector<drum> G[nMax];


void citire() // citire ?!
{
    ifstream input(fin);
    input>>n>>m;
    for (int i=0;i<m;i++)
    {
        int x,y,z;
        input>>x>>y>>z;
        drum d; d.x=y; d.c=z;
        //if (z>0)
            G[x].push_back(d);
    }
    input.close();
}

/*

void push(int x)
{
    dpt++;
    int poz=dpt;
    heap[dpt]=x;
    int padre = poz>>1;
    while (d[heap[padre]]>d[heap[poz]] && poz != 1)
    {
        int aux=heap[padre]; heap[padre]=heap[poz]; heap[poz]=aux;
        poz=padre;
        padre = (poz-poz%2)/2;
    }
}

int pop()
{
    int rez=heap[1];
    heap[1]=heap[dpt--];
    int nod=1;
    int son = d[heap[2]]>d[heap[3]] ? 3:2;
    while(d[heap[nod]]>d[heap[son]] && nod <dpt)
    {
        int aux=heap[nod]; heap[nod]=heap[son]; heap[son]=aux;
        nod=son;
        son = d[heap[2*nod]]<d[heap[2*nod+1]] ? 2*nod:2*nod+1;
    }
    return rez;
}

void decrease(int x)
{
    int poz;
    for (int i=1;i<dpt && heap[i]!=x;i++,poz=i);
    if (heap[poz]!=x)
        return;
    int padre = (poz-poz%2)/2;
    if (padre>0)
    while (d[heap[padre]]>d[heap[poz]] && poz != 1)
    {
        int aux=heap[padre]; heap[padre]=heap[poz]; heap[poz]=aux;
        poz=padre;
        padre = (poz-poz%2)/2;
    }
} */

void minheap(int nod) //mentine proprietatea de min heap
{
    int st=2*nod, dr=2*nod+1, max = 0, aux;
    if (st<=dpt && d[heap[st]] < d[heap[nod]])
        max=st;
    if (dr<=dpt && d[heap[dr]] < d[heap[nod]] && d[heap[dr]]<=d[heap[st]])
        max=dr;
    if (max != 0 )
    {
        aux=heap[nod];
        heap[nod] = heap[max];
        heap[max] = aux;
        minheap(max);
    }
}

void push ( int v ) //insereaza elementul v in heap
{
    int aux;
    heap[++dpt] = v;
    for (int i=dpt; i>1; i= i>>1 )
        if (d[heap[i >> 1]] > d[heap[i]])
        {
        aux=heap[i >> 1];
        heap[i >> 1] = heap[i];
        heap[i] = aux;
        }
}

int pop () // scoate elementul minim din heap
{
    int rez = heap[1];
    heap[1] = heap[dpt--];
    minheap(1);
    return rez;
}

void build_heap()
{
    for (int i=2;i<=n;i++)
        d[i]=inf;
    for (vector<drum>::iterator it = G[1].begin(); it != G[1].end(); it ++)
        d[it->x]=it->c;

    for (int i=2;i<=n;i++)
        push(i);
}

void dijkstra() // Dijkstra
{
    while (dpt>=0) // cat timp mai avem varfuri in heap
    {
        int vs=pop();
        for (vector<drum>::iterator it = G[vs].begin(); it != G[vs].end(); it ++)
            if (d[it->x] > d[vs]+it->c && it->x != first)
            {
                d[it->x] = d[vs]+it->c;
                push(it->x);
            }
    }
}
int main()
{

    citire();
    first=1;
    build_heap();
    dijkstra();
    freopen(fout,"w",stdout);
    for (int i=2;i<=n;i++)
            printf("%d ",d[i]==inf ? 0 : d[i]);
    fclose(stdout);
	return 0;
}