#include <fstream>

using namespace std;

int n, m;

int *dijkstra(int **graf, int src)
{
    int i, min_d, min_i;
    int *dist = new int[n+1];
    bool *sptSet = new bool[n+1];

    for (i = 1; i <= n; i++)
    {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    dist[src] = 0;

    for(int cnt = 1; cnt < n; cnt++)
    {
        min_d = INT_MAX;
        for(i = 1; i <= n; i++)
        {
            if(!sptSet[i] && dist[i] <= min_d)
            {
                min_i = i;
                min_d = dist[i];
            }
        }
        sptSet[min_i] = true;

        if(dist[min_i] == INT_MAX)
            continue;

        for(i = 1; i <= n; i++)
            if (!sptSet[i] && graf[min_i][i] && dist[min_i] + graf[min_i][i] < dist[i])
                dist[i] = dist[min_i] + graf[min_i][i];
    }
    for(i = 1; i <= n; i++)
        if(dist[i] == INT_MAX)
            dist[i] = 0;

    return dist;
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int i, x, y, c;

    f >> n >> m;
    int **mat = new int*[n+1];

    for(i = 1; i <= n; i++)
    {
        mat[i] = new int[n+1];
        for(int j = 1; j <= n; j++)
            mat[i][j] = 0;
    }

    for(i = 0; i < m; i++)
    {
        f >> x >> y >> c;
        mat[x][y] = c;
    }

    int *lung = dijkstra(mat, 1);

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

    return 0;
}