#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <list>
using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

#define inf 10000000

typedef pair<unsigned int, unsigned int> pereche;

vector < list<pereche> > graf;
list <pereche>::iterator it;
vector <unsigned int> dist;
vector <bool> vizitat;

struct compare{
    bool operator() (const int &i, const int &j){
        return dist[i] > dist[j];
    }
};

priority_queue <unsigned int, vector<unsigned int>, compare> coada;
int n, m, start = 1;

void citire(){
    unsigned int x, y, c;
    f >> n >> m;

    graf.resize(n+1);
    dist.resize(n+1, inf);
    vizitat.resize(n+1);

    for(int i = 1; i <= m; ++i){
        f >> x >> y >> c;
        graf[x].push_back(pereche(y, c));
    }
    f.close();
}

void dijkstra(){
    unsigned int top;
    coada.push(start);
    dist[start] = 0;

    while(!coada.empty()){
        top = coada.top();
        coada.pop();

        for(it = graf[top].begin(); it != graf[top].end(); ++it)
            if(dist[it->first] > it->second + dist[top]){
                dist[it->first] = it->second + dist[top];
                coada.push(it->first);
            }
    }
}

void afisare(){
    for(int i = 2; i <= n; ++i)
        if(dist[i] == inf) g << "0 ";
            else g << dist[i] << " ";
    g.close();
}

int main(){
    citire();
    dijkstra();
    afisare();

    return 0;
}