#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <fstream>

using namespace std;
typedef std::pair<int, int> edge;

std::vector<int> shortest_path(const std::vector<std::vector<edge> >& graph, const int source){
    int N = graph.size();
    
    std::set<std::pair<int,int> > S;
    
    std::vector<int> dist;
    for(int i = 0; i <= N; i++){
        dist.push_back(INT_MAX);
    }  
    
    dist[source] = 0;

    S.insert({0, source});

    while(!S.empty()){
        int x = S.begin()->second;
        S.erase(S.begin());
        for(edge e : graph[x]){
            int y = e.first;
            int c = e.second;
            if(dist[y] > dist[x] + c){
                if(dist[y] != INT_MAX){
                    S.erase(S.find({y, dist[y]}));
                }
                dist[y] = dist[x] + c;
                S.insert({dist[y], y});
            }
        }
    }

    return dist;
}

int main(){
	std::ifstream cin("dijkstra.in");
	std::ofstream cout("dijkstra.out");
	int N, M;
	cin >> N >> M;
	std::vector<std::vector<edge> > graph;

	for(int i = 0; i<=N; i++){
		std::vector<edge> v;
		graph.push_back(v);
	}

	for(int i = 0,x,y,z; i < M; i++){
		cin >> x >> y >> z;
		graph[x].push_back({y,z});		
	}

	std::vector<int> dist = shortest_path(graph, 1);
	
	for(int i = 1; i<=N;i++){
		cout << (dist[i] == INT_MAX ? 0 : dist[i]) << ' ';
	}
}