/*
 * =====================================================================================
 *
 *       Filename:  IA_dijkstra.cpp
 *
 *    Description: http://www.infoarena.ro/problema/dijkstra 
                   Graful este orientat.  
 *
 *        Version:  1.0
 *        Created:  06/21/2015 13:13:34
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc  
 *          email:  
 *   Organization:  
 *
 * =====================================================================================
 */

#include <iostream>
#include <fstream> 
#include <vector>
#include <utility>
#include <queue>
#include <climits>

using namespace std;

vector<vector<pair<int, int> > > graph;

class Cmp {
public:
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return (a.second < b.second)? true: false; 
    }
};

vector<int> dijkstra(int vertex, int n, int m) {
    vector<int> distance(n + 1, INT_MAX);
    priority_queue<pair<int, int>, 
                   vector<pair<int, int> >, 
                   Cmp> pq;

    distance[vertex] = 0;
    pq.push(make_pair(vertex, 0)); 

    while (!pq.empty()) {
       int y    = pq.top().first;
       int cost = pq.top().second; 

       pq.pop();

       for (int i = 0; i < graph[y].size(); i++) {
           if (distance[graph[y][i].first] > cost + graph[y][i].second) {
               
               distance[graph[y][i].first] = cost + graph[y][i].second; 
               pq.push(make_pair(graph[y][i].first, 
                                 distance[graph[y][i].first])); 
           }
       } /* for */
    } /* while */

    return distance;
}

int main() { 
    int n, m;
    
    ifstream input("dijkstra.in");
    ofstream output("dijkstra.out");

    input >> n >> m;
    
    vector<pair<int, int> > row;
    for (int i = 0; i <= n; i++) 
        graph.push_back(row);

    for (int i = 0; i < m; i++) {
        int x, y, cost; 

        input >> x >> y >> cost;
        graph[x].push_back(make_pair(y, cost)); // oriented graph
    }

    vector<int> distance = dijkstra(1, n, m);

    for (int i = 2; i <= n; i++) {
        output << distance[i] << ' ';
    }

    input.close();
    output.close();

    return 0;
}