#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,heap[250001],fin,lista[250001],cost[250001],urm[250001],inc[50001],dist[50001];
bool vizitat[50001];
int inheap[50001];
void up(int poz)
{
    int i=poz;
    while(dist[heap[i]]<dist[heap[i/2]])
    {
        int aux=heap[i];
        heap[i]=heap[i/2];
        heap[i/2]=aux;
        inheap[heap[i]]=i;
        inheap[heap[i/2]]=i/2;
        i/=2;
    }
}
void adauga(int x)
{
    fin++;
    heap[fin]=x;
    inheap[x]=fin;
    up(fin);
}
void del()
{
    int poz=1;
    inheap[heap[1]]=0;
    heap[poz]=heap[fin--];
    int minim;
    while(2*poz<=fin)
    {
        if(2*poz+1<=fin)
            if(dist[heap[2*poz]]<dist[heap[2*poz+1]])
                minim=2*poz;
            else minim=2*poz+1;
        else minim=2*poz;
        if(dist[heap[poz]]>dist[heap[minim]])
        {
            int aux=heap[poz];
            heap[poz]=heap[minim];
            heap[minim]=aux;
            inheap[heap[poz]]=poz;
            inheap[heap[minim]]=minim;
            poz=minim;

        }else return ;
    }
}
int main()
{
    f>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        lista[++fin]=y;
        urm[fin]=inc[x];
        inc[x]=fin;
        cost[fin]=c;
    }
    for(int i=2;i<=n;i++)
        dist[i]=1999999999;
    fin=1;

    heap[1]=1;
    while(fin)
    {
        vizitat[heap[1]]=true;
        for(int i=inc[heap[1]];i;i=urm[i])
            if(dist[lista[i]]>dist[heap[1]]+cost[i])
                {
                    dist[lista[i]]=dist[heap[1]]+cost[i];
                    if(!vizitat[lista[i]])
                    {
                        if(!inheap[lista[i]])
                        {
                            adauga(lista[i]);
                        }else {
                            up(inheap[lista[i]]);
                        }
                    }
                }
        del();
    }
    for(int i=2;i<=n;i++)
        if(dist[i]!=1999999999)
            g<<dist[i]<<" ";
        else g<<"0 ";
    return 0;
}