#include<cstdio>
#include<iostream>
#include<climits>
#include<vector>
#define inf INT_MAX/2
using namespace std;

vector < pair<int,int> > lv[50001];

vector < pair<int,int> >::iterator ii;

bool viz[50001];
int d[50001],t[50001],ind_heap[50001],nod_heap[50001],heap[50001];

int main()
{
    FILE *f=fopen("dijkstra.in","r");
    int n,m,x,y,c,i,nh=0,nodc;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&c);
        lv[x].push_back(make_pair(y,c));
    }
    viz[1]=1;
    for(i=1;i<=n;i++)t[i]=-1;
    t[1]=0;
    for(i=1;i<=n;i++)d[i]=inf;
    d[1]=0;
    for(ii=lv[1].begin();ii!=lv[1].end();ii++)
    {
        d[ii->first]=ii->second;
        t[ii->first]=1;
    }
    //construiesc heap-ul din vectorul d, cu toate d-urile in afara de cel egal cu 0, adica al lui 1
    ind_heap[1]=-1;
    for(i=2;i<=n;i++)
    {
        //lipesc mai intii in heap valoarea d[i] la primul indice disponibil, adik dupa celelalte
        ++nh;
        heap[nh]=d[i];
        ind_heap[i]=nh;
        nod_heap[nh]=i;
        //refac traseul dintre nodul proaspat adaugat shi radacina:
        nodc=nh;
        while(nodc/2 && heap[nodc]<heap[nodc/2])
        {
            swap(heap[nodc],heap[nodc/2]);
            swap(nod_heap[nodc],nod_heap[nodc/2]);
            x=nod_heap[nodc];y=nod_heap[nodc/2];
            swap(ind_heap[x],ind_heap[y]);
            nodc=nodc/=2;
        }
    }
    int k,dmin;
    for(i=2;i<=n-1;i++)
    {//aplicam Dijkstra: Alegem nodul minim care este in virful heap-ului:
        dmin=heap[1];
      //vedem la ce nod se refera vf. heap-ului:
        k=nod_heap[1];viz[k]=1;
      //verificam ce distantze sunt actualizate de genu' dmin+cost(k,*)
        for(ii=lv[k].begin();ii!=lv[k].end();ii++)
            if(!viz[ii->first] && dmin+ii->second<d[ii->first])
            {
                d[ii->first] = dmin+ii->second;
                t[ii->first] = k;
                nodc=ind_heap[ii->first];
                heap[nodc]=d[ii->first];
                while(nodc/2 && heap[nodc]<heap[nodc/2])
                {
                    swap(heap[nodc],heap[nodc/2]);
                    swap(nod_heap[nodc],nod_heap[nodc/2]);
                    x=nod_heap[nodc];y=nod_heap[nodc/2];
                    swap(ind_heap[x],ind_heap[y]);
                    nodc/=2;
                }
            }
        //facem shtergerea efectiva din heap: mai intii aducem ultimul nod pe poz. 1
        swap(heap[1],heap[nh]);
        swap(nod_heap[1],nod_heap[nh]);
        x=nod_heap[1];y=nod_heap[nh];
        swap(ind_heap[x],ind_heap[y]);
        nh--;ind_heap[k]=-1;
        int fiu;nodc=1;
        while(1)
        {
            fiu=2*nodc;
            if(fiu>nh)break;
            if(fiu+1<=nh&& heap[fiu+1]<heap[fiu])fiu++;
            if(heap[nodc]<heap[fiu])break;
            swap(heap[nodc],heap[fiu]);
            swap(nod_heap[nodc],nod_heap[fiu]);
            x=nod_heap[nodc];y=nod_heap[fiu];
            swap(ind_heap[x],ind_heap[y]);
            nodc=fiu;
        }
    }
    f=fopen("dijkstra.out","w");
    for(i=2;i<=n;i++)
        fprintf(f,"%d ",d[i]==inf?0:d[i]);
    return 0;
}