#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

void Dijkstra(int nod_pornire, int n, vector < vector < pair < int,int > > > lista_vecini, vector < int > &distante){
    priority_queue < pair < int, int >, vector < pair <int, int> >, greater < pair < int, int > > > coada_prioritati;
    vector < int > apartine_Coada(n+1, 0);
    coada_prioritati.push(make_pair(0,nod_pornire));
    distante[nod_pornire] = 0;
    while( coada_prioritati.size() != 0 ){
        int x = coada_prioritati.top().second;
        coada_prioritati.pop();
        if( apartine_Coada[x] == 0 ){
            apartine_Coada[x] = 1;
            for( int i = 1; i < lista_vecini[x].size(); i++ ){
                if( distante[ lista_vecini[x][i].first ] > distante[x] + lista_vecini[x][i].second ){
                    distante[ lista_vecini[x][i].first ] = distante[x] + lista_vecini[x][i].second;
                    coada_prioritati.push(make_pair(distante[lista_vecini[x][i].first ], lista_vecini[x][i].first));
                }
            }
        }
    }
}

int main(){
    int n,m;
    vector < vector < pair < int,int > > > lista_vecini;
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin >> n >> m;
    int intrare, iesire, cost;
    vector < pair < int, int > > v(1,make_pair(-1,-1));
    for( int i = 0; i <= n+1; i++ ){
        lista_vecini.push_back(v);
    }
    for( int i = 1; i <= m; i++ ){
        fin >> intrare >> iesire >> cost;
        lista_vecini[intrare].push_back(make_pair(iesire,cost));
    }
    vector < int > distante(n+1, 999999);
    Dijkstra(1,n,lista_vecini,distante);
    for( int i = 2; i <= n; i++ ){
        if( distante[i] == 999999 ) fout << 0 << " ";
        else fout << distante[i] << " ";
    }
    return 0;
}