#include <iostream>
#include <fstream>

using namespace std;

fstream f,g;

unsigned int n,m,dist[50001],prez[50001],ord[50001],i,j,k,l,ads,adl;

struct lst
{
    lst *urm;
    unsigned int dist,orig;
}*cale[50001][2],*u;

void add(unsigned int j,unsigned int k,unsigned int l)
{
    lst *n=new lst;
    n->urm=NULL;
    n->dist=l;
    n->orig=k;
    if(cale[j][0]==NULL)cale[j][0]=n;
    else cale[j][1]->urm=n;
    cale[j][1]=n;
}


int main()
{
    f.open("dijkstra.in",ios_base::in);
    g.open("dijkstra.out",ios_base::out);
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>j>>k>>l;
        add(j,k,l);
    }
    ord[1]=1;
    prez[1]=1;
    dist[1]=0;
    l=1;
    while(l<n)
    {
        adl=-1;
        for(i=1;i<=l;i++)for(u=cale[ord[i]][0];u!=NULL;u=u->urm)if(dist[ord[i]]+u->dist<adl&&prez[u->orig]==0)
        {
            adl=dist[ord[i]]+u->dist;
            ads=u->orig;
        }
        dist[ads]=adl;
        prez[ads]=1;
        ord[l+1]=ads;
        l++;
    }
    for(i=2;i<=n;i++)g<<dist[i]<<' ';
}