#include<ifstream>
#include<fstream.h>
int v[250010][3],c[50010],i,x,y,j,ok;
int main()
{
    /*freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);*/
    ifstream f("dijkstra.in");
    ofstream h("dijkstra.out");
    //scanf("%d %d",&x, &y);
    f>>x>>y;
    for(i=2;i<=x;i++)c[i]=2000000000;
    for(i=1;i<=y;i++)
    {  
       // scanf("%d %d %d",&v[i][0],&v[i][1],&v[i][2]);
       f>>v[i][0]>>v[i][1]>>v[i][2];
        if(v[i][0]==1)c[v[i][1]]=v[i][2];
    }
    while(!ok)
    {
        ok=1;
        for(j=1;j<=y;j++)
        {   
            if(c[v[j][1]]>c[v[j][0]]+v[j][2])
                {
                    c[v[j][1]]=c[v[j][0]]+v[j][2];
                    ok=0;
                }
        }
    }
    for(i=2;i<=x;i++)
       if(c[i]<2000000000)
       h<<c[i]<<" ";
       //printf("%d ",c[i]);
        else h<<"0 "; 
        //printf("0 ");
    return 0;
    f.close();
    h.close();
}