#include<fstream>
using namespace std;
int a,b,c,i,n,m,k,x;
long long viz[50002];
struct nod
{
    int x,lungime;
    nod *leg;
};
nod *first,*last,*q,*p,*v[50002];
int main()
{
     ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for(i=2;i<=n;i++)
    {
        v[i]=0;
        viz[i]=0;
    }
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        p=new nod;
        p->x=b;
        p->lungime=c;
        p->leg=v[a];
        v[a]=p;
    }
    first=new nod;
    first->x=1;
    first->lungime=0;
    first->leg=0;
    last=first;
    viz[first->x]=0;
    while(first!=0)
    {
        x=first->x;
        for(p=v[x];p!=0;p=p->leg)
        {
            if(viz[p->x]==0)
            {
                viz[p->x]=viz[x]+p->lungime;
                q=new nod;
                q->x=p->x;
                q->lungime=p->lungime;
                q->leg=0;
                last->leg=q;
                last=q;
            }
            else
            {
                if(viz[p->x]>viz[x]+p->lungime)
                {
                    viz[p->x]=viz[x]+p->lungime;
                    q=new nod;
                    q->x=p->x;
                    q->lungime=p->lungime;
                    q->leg=0;
                    last->leg=q;
                    last=q;
                }
            }
        }
        p=first;
        first=first->leg;
        delete p;
    }
    for(i=2;i<=n;i++)
    {
        fout<<viz[i]<<" ";
    }
    fin.close();
    fout.close();
    return 0;
}