#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 1 << 16;


int father(int node){

    return (node - 1) >> 1;
}

int left_son(int node){

    return (node << 1) + 1;
}

int right_son(int node){

    return (node << 1) + 2;
}

void sift_up(int node, vector<int>& positions, const vector<int>& distances, vector<int>& heap){

    int current = positions[node];
    while(current > 0 && distances[heap[current]] < distances[heap[father(current)]]){

        swap(positions[heap[current]], positions[heap[father(current)]]);
        swap(heap[current], heap[father(current)]);
        current = father(current);
    }
}

void sift_down(int node, vector<int>& positions, const vector<int>& distances, vector<int>& heap){

    int current = positions[node], better_son = -1;

    while(better_son){

        better_son = 0;
        if(left_son(current) < heap.size() && distances[heap[left_son(current)]] < distances[heap[current]]){
            better_son = left_son(current);
        }
        if(right_son(current) < heap.size() && distances[heap[right_son(current)]] < distances[heap[current]] && distances[heap[right_son(current)]] < distances[heap[left_son(current)]]){
            better_son = right_son(current);
        }

        if(better_son){
            swap(positions[heap[current]], positions[heap[better_son]]);
            swap(heap[current], heap[better_son]);
            current = better_son;
        }
    }
}

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

    vector<int> distances, positions,heap;

    for(int i = 0; i < graph.size(); ++i){
        heap.push_back(i);
        distances.push_back(INT32_MAX);
        positions.push_back(i);
    }
    distances[start_node] = 0;
    
    while(!heap.empty()){

        int current_node = heap[0];
        positions[heap[0]] = -1;
        positions[heap[heap.size() - 1]] = 0;
        heap[0] = heap[heap.size() - 1];
        heap.pop_back();
        sift_down(heap[0], positions, distances, heap);

        for(int i = 0; i < graph[current_node].size(); ++i){
            if(distances[current_node] != INT32_MAX && distances[graph[current_node][i].first] > distances[current_node] + graph[current_node][i].second){
                
                distances[graph[current_node][i].first] = distances[current_node] + graph[current_node][i].second;
                sift_up(graph[current_node][i].first, positions, distances, heap);
            }
        }    
    }



    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;
}