#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
struct Muchie{
    int nod, cost;
};
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<vector<Muchie>> lista;
vector<int> distante;
vector<bool> vizitate;

void dijkstra(){
    priority_queue<pair<int, int>> coada;
    coada.push({0, 1});
    while(!coada.empty()){
        pair<int, int> pereche = coada.top();
        int nod = pereche.second;
        coada.pop();
        if (vizitate[nod]) continue;
        vizitate[nod] = true;
        for(auto& muchie : lista[nod]){
            if(!vizitate[muchie.nod]){
                if(distante[muchie.nod] > distante[nod] + muchie.cost)
                {
                    distante[muchie.nod] = distante[nod] + muchie.cost;
                    coada.push({-distante[muchie.nod], muchie.nod});
                }
            }
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    lista.resize(n + 1);
    for(int i = 0; i < m; i++){
        int s, d, c;
        fin >> s >> d >> c;
        lista[s].push_back({d, c});
    }
    distante.resize(n + 1, INT_MAX);
    vizitate.resize(n + 1, false);
    distante[1] = 0;
    dijkstra();
    for(int i = 2; i <= n; i++)
        fout << distante[i] <<' ';

    return 0;
}