#include <iostream>
#include <fstream>

using namespace std;
struct nod
{
    int info;
    int distanta;
    nod *next;
}*L[50001];
int n,m,d[50001],viz[50001];
long long pinf=999999999;
void citire()
{
    ifstream f ("dijkstra.in");
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        nod *q;
        q=new nod;
        int x,y,c;
        f>>x>>y>>c;
        q->info=y;
        q->distanta=c;
        q->next=L[x];
        L[x]=q;
    }
    for(int i=2; i<=n; i++)
        d[i]=pinf;
}
void actualizeaza_drum(int varf)
{
    nod *q=L[varf];
    while(q!=NULL)
    {
        if(d[q->info]>d[varf]+q->distanta)
            d[q->info]=d[varf]+q->distanta;
        q=q->next;
    }
}
int cauta_varf()
{
    int min=pinf;
    int varf;
    for(int i=1; i<=n; i++)
        if(viz[i]==0&&min>d[i])
        {
            min=d[i];
            varf=i;
        }
    return varf;
}
void djikstra()
{
    int varf=1;
    for(int i=1; i<=n-1; i++)
    {
        actualizeaza_drum(varf);
        viz[varf]=1;
        varf=cauta_varf();
    }
}
int main()
{
    ofstream g ("dijkstra.out");
    citire();
    djikstra();
    for(int i=2; i<=n; i++)
        if(d[i]==pinf)
            g<<"0 ";
        else
            g<<d[i]<<" ";
    return 0;
}