#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define nmax 50005
#define inf (1<<30)
#define weight first
#define node second
using namespace std;

set <pair<int, int> > s;
vector <pair<int, int> > v[nmax];
int dist[nmax];

void get_data(int &n){
    int m, x, y, w;
    ifstream fin ("dijkstra.in");
    fin >> n >> m;
    for(int i= 1; i<= m; i++){
        fin >> x >> y >> w;
        v[x].push_back(make_pair(w, y));
    }
}

void dijkstra(int n){
    for(int i= 2; i<= n; i++)   dist[i]= inf;
    s.insert(make_pair(0, 1));
    while(!s.empty()){
        int current= s.begin()-> node;
        int current_value= s.begin()-> weight;
        s.erase(s.begin());
        for(auto x: v[current])
            if(dist[x.node]> dist[current]+ x.weight){
                dist[x.node]= dist[current]+ x.weight;
                s.insert(make_pair(dist[x.node], x.node));
            }
    }
    ofstream fout ("dijkstra.out");
    for(int i= 2; i<= n; i++){
        if(dist[i]== inf)   fout << "0" << " ";
        else    fout << dist[i] << " ";
    }
}

int main(){
    int n;
    get_data(n);
    dijkstra(n);
    return 0;
}