/*
 * =====================================================================================
 *
 *       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);
    vector<bool> visited(n + 1, false); 
    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();
        
        if (visited[x])
        	continue;
        visited[x] = true;
         
        for (auto it = graph[x].begin(); it != graph[x].end(); it++) {
            int y    = it->first;
            int cost = it->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] == INT_MAX? 0: distance[i]) << ' ';
    }
    output << '\n';
    
    input.close();
    output.close();
 
    return 0;
}