//dijkstra cu heapuri
#include <fstream>
#define lg_max 50001
#define infinit 1<<30
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)
    {
         int c=poz;
         if ((poz<<1)>nr)
             return;
         c=poz<<1;
         if ( c+1<=nr)
             if ( dist[heap[c+1]] < dist[heap[c]])
                 c++;
         if (dist[heap[poz]]<= dist[heap[c]])
             return;
         viz[heap[poz]]=c;
         viz[heap[c]]=poz;
         schimba(poz,c);
         poz=c;
    }

}

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();
    nr=1;
    while (nr)
    {
        min=heap[1];
        schimba(1,nr);
        viz[heap[1]]=1;
        nr--;
        in_jos(1);
        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)
                {
                    nr++;
                    heap[nr]=i->inf;
                    viz[heap[nr]]=nr;
                    in_sus(nr);
                }
                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;
}