#include <fstream>
#define lg_max 50001
#define infinit 1<<29
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod
{
    int inf,cost;
    nod *next;
} *sir[lg_max];

int heap[lg_max],dist[lg_max],viz[lg_max];
int n,m,nr;

void adauga(int a,int b,int c)
{
    nod *q=new nod;
    q->inf=a;
    q->cost=c;
    q->next=sir[b];
    sir[b]=q;
}

void citire()
{
    fin>>n>>m;
    int a,b,cost;
    for (int i=0;i<m;i++)
    {
        fin>>a>>b>>cost;
        adauga(b,a,cost);
    }
}

void initializare()
{
    for (int i=1;i<=n;i++)
    {
        heap[i]=i;
        dist[i]=infinit;
        viz[i]=-1;
    }
    nr++;
    dist[1]=0;
    heap[1]=1;
    viz[1]=1;
}

void schimba(int a,int b)
{
    int aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
}

void in_jos(int poz)
{
    while (poz<=nr)
    {
        if (poz<<1>nr)
            return ;
        if (dist[heap[poz]]>dist[heap[poz<<1]])
        {
            viz[heap[poz]]=poz<<1;
            viz[heap[poz<<1]]=poz;
            schimba(poz,poz<<1);
            poz=poz<<1;
        }
        else
            if (dist[heap[poz]]>dist[heap[(poz<<1)+1]])
            {
                viz[heap[poz]]=(poz<<1)+1;
                viz[heap[(poz<<1)+1]]=poz;
                schimba(poz,(poz<<1)+1);
                poz=(poz<<1)+1;
            }
            else
                return ;
    }
}

void in_sus(int poz)
{
    while (poz>1)
    {
        if (dist[heap[poz]]<dist[heap[poz>>1]])
        {
            viz[heap[poz]]=poz>>1;
            viz[heap[poz>>1]]=poz;
            schimba(poz,poz<<1);
            poz=poz>>1;
        }
        else
            return ;
    }
}

void dijkstra()
{
    int min;
    initializare();
    while (nr)
    {
        min=heap[1];
        schimba(1,nr);
        nr--;
        in_jos(nr);
        for (nod *i=sir[min];i;i=i->next)
            if (dist[i->inf]>dist[min]+i->cost)
            {
                dist[i->inf]=dist[min]+i->cost;
                if (viz[i->inf]==-1)
                {
                    heap[++nr]=i->inf;
                    viz[nr]=nr;
                    in_sus(nr-1);
                }
                else
                in_sus(viz[i->inf]);

            }
    }
}

void afisare()
{
    for (int i=2;i<=n;i++)
        fout<<((dist[i]==infinit)?0:dist[i])<<" ";
}

int main ()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}