#include <iostream>
#include <fstream>
#include <vector>

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

int n, m;
struct vertex
{
    int cost, legatura;
};
std::vector<vertex> muchie[5005];

int visited[5005];

void dfs(int &nod, int &valoare)
{
    for(int i = 0; i < muchie[nod].size(); i++)
    {
        if(visited[muchie[nod][i].legatura] > valoare + muchie[nod][i].cost)
        {
            visited[muchie[nod][i].legatura] = valoare + muchie[nod][i].cost;
            dfs(muchie[nod][i].legatura, visited[muchie[nod][i].legatura]);
        }
    }
}

void ciorba()
{
    for(int i = 2; i <= n; i++)
    {
        visited[i] = 1000000001;
    }

    int vacute_mov = 1;
    int valoare = 0;///fara numar
    dfs(vacute_mov, valoare);

    for(int i = 2; i <= n; i++)
    {
        fout<<visited[i]<<' ';
    }
}

void citire()
{
    fin>>n>>m;
    int x, y, z;

    for(int i = 0; i < m; i++)
    {
        fin>>x>>y>>z;

        vertex nod1;
        nod1.cost = z;
        nod1.legatura = y;

        muchie[x].push_back(nod1);
    }

    ciorba();
}

int main()
{
    citire();
    return 0;
}