#include <stdio.h>
#include <deque>
using namespace std;
FILE *f,*g;

int start[50002],t[4][250002],drum[50002],n,m,fr[50002],ok;
deque <int>q;

void write()
{
    int i;
    if(!ok)
        for(i=2;i<=n;++i)
            if(drum[i]!=2000000000)
                fprintf(g,"%d ",drum[i]);
            else
                fprintf(g,"0 ");
}
void bellmanford()
{
    int no,nod,dr;
    q.push_back(1);
    drum[1]=0;
    while(!q.empty())
    {
        nod=q.front();
        q.pop_front();
        no=start[nod];
        while(no)
        {
            dr=t[3][no];
            if(drum[t[0][no]]>dr+drum[nod])
            {
                drum[t[0][no]]=dr+drum[nod];
                 q.push_back(t[0][no]);
            }
            no=t[1][no];
        }
    }
}
int main()
{
    int i,j,k=0,o;
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(o=1;o<=m;++o)
    {
        ++k;
        fscanf(f,"%d %d %d",&i,&j,&t[3][k]);
        t[0][k]=j,t[1][k]=start[i],start[i]=k;
    }
    for(i=1;i<=n;++i) drum[i]=2000000000;
    bellmanford();
    write();
    fclose(f);
    fclose(g);
    return 0;
}