#include <cstdio>

const int inf = 1000000;

using namespace std;

int n,m,c[1000][1000];
int d[1000],v[1000],t[1000];

void read()
{
    int x,y,co;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%i %i",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)
                c[i][j] = 0;
            else
                c[i][j] = inf;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%i %i %i",&x,&y,&co);
        c[x][y]=co;
    }
}

void Pasul1()
{
    for(int i=1;i<=n;i++)
    {
        d[i] = c[1][i];
        if(i != 1)
            v[i]=0;
        else
            v[i]=1;
        if(i==1 || c[1][i] == inf)
            t[i] = 0;
        else
            t[i] = 1;
    }
}

int minim()
{
    int min = 9999999;
    int loc = 0;
    for(int i=1;i<=n;i++)
    {
        if(v[i] == 0 && d[i] != inf)
        {
            if(d[i] < min)
            {
                min=d[i];
                loc = i;
            }
        }
    }
    return loc;
}

void Pasul2()
{
    int loc;
    for(int i=2;i<=n-1;i++)
    {
        loc = minim();
        v[loc] = 1;
        for(int j=1;j<=n;j++)
        {
            if(v[j] == 0)
            {
                if(d[j] > d[loc] + c[loc][j])
                {
                    d[j] = d[loc] + c[loc][j];
                    t[j] = loc;
                }
            }
        }
    }
}
/*
void Afisare()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%i ",c[i][j]);
        printf("\n");
    }
}

void Afisare2()
{
    printf("D = ");
    for(int i=1;i<=n;i++)
        printf("%i ",d[i]);
    printf("\nV = ");
    for(int i=1;i<=n;i++)
        printf("%i ",v[i]);
    printf("\nT = ");
    for(int i=1;i<=n;i++)
        printf("%i ",t[i]);
}
*/
int main()
{
    read();
    //Afisare();
    Pasul1();
    Pasul2();
    //Afisare2();
    for(int i=2;i<=n;i++)
        printf("%i ",d[i]);
    return 0;
}