#include <fstream>
#include <climits>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod
{
    int x,cost;
    nod*urm;
}*A[250005],*p;

int n,m,i,a,b,c,culoare[250005],cc[250005],coada[250005],in=1,sf=0;

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        p=new nod;
        p->x=b;
        p->cost=c;
        p->urm=A[a];
        A[a]=p;
    }
    for(i=1;i<=n;i++)
        cc[i]=0;
    cc[1]=0;
    culoare[1]=2;
    p=A[1];
    while(p)
    {
        cc[p->x]=p->cost;
        culoare[p->x]=1;
        coada[++sf]=p->x;
        p=p->urm;
    }
    int k,cd;
    while(in<=sf)
    {
        p=A[coada[in]];
        while(p)
        {
            k=p->x;
            cd=p->cost;
            if((culoare[p->x]==2 && cc[p->x]>cc[coada[in]]+p->cost)|| !culoare[p->x])
                culoare[p->x]=1,cc[p->x]=cc[coada[in]]+p->cost,coada[++sf]=p->x;
            else
                if(culoare[p->x] == 1 && cc[p->x]>cc[coada[in]]+p->cost)
                    cc[p->x]=cc[coada[in]]+p->cost;
            p=p->urm;
        }
        culoare[coada[in]]=2;
        in++;
    }
    for(i=2;i<=n;i++) g<<cc[i]<<' ';
    return 0;
}