#include <fstream>
#include <iostream>

using namespace std ;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int main ()
{
    int i,j,n,matrice [101][101],x,m;
    int int_max = 32000;
    x=1;
    f>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
        matrice [i][j] == 0;
    for (i=1;i<=m;i++)
    {
        int v1,v2,v3;
        f>>v1>>v2>>v3;
        matrice [v1][v2] = v3;
    }


    int distance [101],gasit [101],punct;


    for (i=1;i<=n;i++)
    {
        distance [i] = int_max;
        gasit [i] = 0;
    }
    distance [x] = 0;
    int nimic_nou =1;
    for (i=1;i<n && nimic_nou;i++)
    {
        nimic_nou = 0;
        int dist_min = int_max;
        for (j=1;j<=n;j++)
        {
            if (gasit [j] == 0)
            if (dist_min > distance[j])
            {
                dist_min = distance[j];
                punct = j;
                nimic_nou =1;
            }
        }
        gasit [punct] =1;

        for (j=1;j<=n;j++)
            if (gasit [j] == 0)
                if ( matrice [punct][j] !=0)
                    if (distance [punct] != int_max)
                        if (distance [j] > distance [punct] + matrice [punct][j])
                            distance [j] = distance [punct] + matrice [punct][j];


    }

    for (i=2;i<=n;i++)
        g << distance [i] << " ";
}