#include <iostream>

#define infinit 5001


using namespace std;


int mat[3000][3000],n,m;


void init()
{
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
            {
                if(i==j) mat[i][j]=-1;
                else mat[i][j]=infinit;
            }
}


void citire()
{
    scanf("%d%d",&n,&m);

    init();

    for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);

            mat[x][y]=z;
        }




}


void dijkstra(int k)
{
    int s[3000]={0},d[3000],t[3000]={0};

    for(int i=1;i<=n;i++)
        {
            d[i]=mat[k][i];
            if(d[i]<infinit&&d[i]>=0) t[i]=k;
        }
    s[k]=1;

    for(int i=1;i<=n-1;i++)
        {
            int minim=infinit,poz;
            for(int j=1;j<=n;j++)
                {
                    if(s[j]==0&&d[j]<minim)
                        {
                            poz=j;
                            minim=d[j];
                        }
                }
            s[poz]=1;
            for(int j=1;j<=n;j++)
                {
                    if(s[j]==0)
                        if(d[j]>d[poz]+mat[poz][j])
                            {
                                d[j]=d[poz]+mat[poz][j];
                                t[j]=poz;
                            }
                }

        }
    for(int j=2;j<=n;j++)
        {
            if(d[j]==infinit) printf("0 ");
            else printf("%d ",d[j]);
        }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    citire();

    dijkstra(1);



    return 0;
}