#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define nmax 50010
#define inf 2000000000
struct nod
{
    int val,cost;
    nod *urm;
};
typedef nod *pnod;
pnod p,v[nmax];
int dist[nmax],poz[nmax],heap[nmax],cate_heap;
void ad(int x,int y,int c)
{
    p=new nod;
    p->val=y;
    p->cost=c;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
void upheap(int k)
{
    while(k>1 and dist[heap[k]]<dist[heap[k/2]])
    {
        swap(heap[k],heap[k/2]);
        swap(poz[heap[k]],poz[heap[k/2]]);
        k/=2;
    }
}
int ind;
void downheap(int k)
{
    do
    {
        ind=0;
        if(k*2<=cate_heap)
        {
            ind=k*2;
            if(ind+1<=cate_heap and dist[heap[ind+1]]<dist[heap[ind]])
                ind+=1;
            if(dist[heap[ind]]<dist[heap[k]])
            {
                swap(heap[ind],heap[k]);
                swap(poz[heap[ind]],poz[heap[k]]);
                k=ind;
            }
            else
                ind=0;
        }
    }while(ind);
}
int main()
{
    int n,m,i,minim,x,y,c;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
        dist[i]=inf;
        poz[i]=-1;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
    }
    dist[1]=0;
    cate_heap=1;
    poz[1]=1;
    heap[1]=1;
    while(cate_heap)
    {
        minim=heap[1];
        swap(heap[1],heap[cate_heap]);
        poz[heap[1]]=1;
        cate_heap-=1;
        downheap(1);
        p=v[minim]->urm;
        while(p)
        {
            if(dist[minim]+p->cost<dist[p->val])
            {
                dist[p->val]=dist[minim]+p->cost;
                if(poz[p->val]==-1)
                {
                    cate_heap+=1;
                    heap[cate_heap]=p->val;
                    poz[p->val]=cate_heap;
                    upheap(cate_heap);
                }
                else
                {
                    upheap(poz[p->val]);
                }
            }
            p=p->urm;
        }
    }
    for(i=2;i<=n;i++)
        if(dist[i]==inf)
            g<<"0 ";
        else
            g<<dist[i]<<" ";
    return 0;
}