#include <iostream>
#include <set>
#include <vector>
#include <fstream>
#define MAX 250001

using namespace std;

vector < pair<int,int> > graf[MAX];
    int dist[MAX];

int main(){
    ifstream be("dijkstra.in");
    ofstream ki("dijkstra.out");
    int n, m, to, from, weight;
    be >> n >> m;

    for (int i = 1; i<=m; i++){
        be>>from>>to>>weight;
        graf[from].push_back(make_pair(to, weight));
        if(i>=2)
            dist[i] = INT_MAX;
    }

    set < pair <int,int> > temp;
    temp.insert(make_pair(0,1));

    while(!temp.empty()){
        int node = temp.begin() -> second;
        weight = temp.begin() ->first;
        temp.erase(temp.begin());
        for( vector<pair <int, int> >::iterator it = graf[node].begin(); it != graf[node].end(); it++){
            to = it->first;
            if(dist[to]>dist[node]+weight){
                if(dist[to]!=INT_MAX)
                    temp.erase(temp.find(make_pair(dist[to], to)));
                dist[to]=dist[node]+weight;
                temp.insert(make_pair(dist[to], to));
            }
        }
    }

    for(int i = 2; i <= n;i++){
        if(dist[i] == INT_MAX){
                dist[i] = 0;
        }
            ki << dist[i] << " ";

    }
}