#include <cstdio>
#define nmax 5000
#define INF 10000
using namespace std;
FILE *f1=fopen("dijkstra.in","r"),*f2=fopen("dijkstra.out","w");
int n,m,sursa=1;
int c[nmax][nmax];
int pre[nmax],use[nmax];
int d[nmax];
void init()
{
    int i,j,x,y,cst;
    // Citeste n & m
    fscanf(f1,"%d%d",&n,&m);
    // Initializeaza costurile cu INF
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
    c[i][j]=INF;
    //Citeste m arce
    for(i=1;i<=m;i++)
        {
            fscanf(f1,"%d%d%d",&x,&y,&cst);
            c[x][y]=cst;
        }
    for(i=1;i<=n;i++)
    {
        d[i]=c[sursa][i];
        pre[i]=sursa;
    }
    use[sursa]=1;
    pre[sursa]=0;
}
int main()
{
    int i,vMin,j;
    double dMin;
    init();
    for(j=1;j<n;j++)
    {
        dMin=INF;
        for(i=1;i<=n;i++)
            if(!use[i]&&dMin>d[i])
        {
            dMin=d[i];
            vMin=i;
        }
        use[vMin]=1;
        for(i=1;i<=n;i++)
            if(!use[i]&&d[i]>dMin+c[vMin][i])
        {
            pre[i]=vMin;
            d[i]=dMin+c[vMin][i];
        }
    }
    for(int i=2;i<=n;i++)
        if(d[i]!=INF)
            fprintf(f2,"%d ",d[i]);
        else fprintf(f2,"0 ");
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.