#include <iostream>

using namespace std;
#define inf 10000;
int a[1000][1000],n,m;

void citire()
{
    freopen("dijkstra.in","r",stdin);

    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=inf;

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

void dijkstra()
{
    int d[1000],viz[1000]={0},poz=0;

    d[1]=0;
    viz[1]=1;

    for(int i=1;i<=n;i++)
        d[i]=a[1][i];

    for(int i=1;i<=n-1;i++)
        {
            int dmin=inf;
            for(int j=1;j<=n;j++)
                    if((dmin>d[j])&&(viz[j]==0))
                        {
                            dmin=d[j];
                            poz=j;
                        }
            viz[poz]=1;

            for(int j=1;j<=n;j++)
                {
                    if((!viz[j])&&(d[j]>dmin+a[poz][j]))
                        d[j]=a[poz][j]+dmin;
                }
        }

    freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=n;i++)
        printf("%d ", d[i]);
}


int main()
{
    citire();



    dijkstra();
    return 0;
}