#include<stdio.h>
# include <string.h>
using namespace std;
int i,j,d[50010],poz,min,n,m,a[5000][5000],x,y,z,t[5000];
bool use[50010];
void dijkstra(int p)
{
    int i;
    for (i=1; i<=n; i++)
    {
        d[i]=80000;
        use[i]=false; t[i]=0;
    }
    d[p]=0;
    poz=0;
    bool ok=true;
    for (i=1; i<=n && ok; i++)
    {
        min=80000;
        for (j=1; j<=n; j++)
            if (use[j]==false && d[j]<min)
                      {
                           min=d[j];
                           poz=j;
                      }
        if (min!=80000)
        {
            use[poz]=true;
            for (j=1; j<=n; j++)
                 if (d[j]>d[poz]+a[poz][j] && use[j]==false)
                 { d[j]=d[poz]+a[poz][j];
            t[j]=poz; }
        }
        else ok=false;
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1; i<=n; i++)
         for (j=1; j<=n; j++) a[i][j]=80000;
    for (i=1; i<=m; i++)
    {
        scanf("%d %d %d\n",&x,&y,&z);
        a[x][y]=z;
    }
    dijkstra(1);
    for (i=2; i<=n; i++)
         printf("%d ",d[i]);
    printf("\n");
    return 0;
}