#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

const int MAX_N = 1 << 16;

vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start_node){

    vector<int> distances(graph.size(), INT32_MAX);
    vector<int> minDist(graph.size(), INT32_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    distances[start_node] = 0;
    pq.push(make_pair(0, start_node));
    minDist[start_node]  = 0;
    
    while(!pq.empty()){

        int current_node = pq.top().second;
        pq.pop();
        
        if(distances[current_node] != INT32_MAX){
            for(const auto& vec : graph[current_node]){
                if(distances[vec.first] > distances[current_node] + vec.second){
                
                    distances[vec.first] = distances[current_node] + vec.second;
                    if(distances[vec.first] < minDist[vec.first]){
                        pq.push(make_pair(distances[vec.first], vec.first));
                        minDist[vec.first] = distances[vec.first];
                    }
                    
                }
            }   
        } 
    }

    return distances;
}

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


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


    vector<int> result = dijkstra(graph, 0);
    for(int i = 1; i < result.size(); ++i){
        if(result[i] == INT32_MAX) result[i] = 0;
        cout << result[i] << " ";
    }

    cin.close();
    cout.close();

    return 0;
}