/*
 * =====================================================================================
 *
 *       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 source, int n, int m) {
    vector<int> distance(n + 1, INT_MAX);
    priority_queue<pair<int, int>, 
                   vector<pair<int, int> >, 
                   Cmp> pq;

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

    while (!pq.empty()) {
        int x = pq.top().first;

        pq.pop();

        for (int i = 0; i < graph[x].size(); i++) {
            int y    = graph[x][i].first;
            int cost = graph[x][i].second;

            if (distance[y] > distance[x] + cost) {
                distance[y] = distance[x] + cost;
                pq.push(make_pair(y, distance[y]));
            } /* if */
        } /* 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;
}