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