#include <iostream>
#include <fstream>

#define N 50001
#define Inf 20001

using namespace std;

int** matriceaCosturilor;
int* drumMin;
int* varfMin;
bool* M;
int n, m;

void init();
void afisare();

int main()
{
    int vMin = 1, dMin = 1;
    init();

    for(int i = 1; i < n; i++)
    {
        dMin = Inf;

        for(int j = 1; j <= n; j++)
        {
            if(!M[j] && drumMin[j] < dMin)
            {
                dMin = drumMin[j];
                vMin = j;
            }
        }

        M[vMin] = true;

        for(int j = 1; j <= n; j++)
        {
            if(!M[j] && drumMin[j] > dMin + matriceaCosturilor[vMin][j])
            {
                drumMin[j] = dMin + matriceaCosturilor[vMin][j];
                varfMin[j] = vMin;
            }
        }
    }

    afisare();

    return 0;
}

void init()
{
    ifstream in("dijkstra.in");
    int x, y, c;

    in >> n >> m;

    matriceaCosturilor = new int*[n];

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

    drumMin = new int[n];
    varfMin = new int[n];
    M = new bool[n];

    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            matriceaCosturilor[i][j] = matriceaCosturilor[j][i] = Inf;
        }
    }

    for(int i = 1; i <= m; i++)
    {
        in >> x >> y >> c;

        matriceaCosturilor[x][y] = c;
    }

    for(int i = 1; i <= n; i++)
    {
        drumMin[i] = matriceaCosturilor[1][i];
    }

    for(int i = 1; i <= n; i++)
    {
        varfMin[i] = 1;
    }

    varfMin[1] = 0;
    M[1] = true;
}

void afisare()
{
    ofstream out("dijkstra.out");

    for(int i = 2; i <= n; i++)
    {
        out << drumMin[i] << " ";
    }
}