/*
 * e_009_dijkstra.cpp
 *
 *  Created on: May 24, 2015
 *      Author: Marius
 */

#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <limits>
#include <string>
#include <fstream>
#include <utility>

//int e_009_dijkstra()
int main()
{
    string in_file = "dijkstra.in";
    string out_file = "dijkstra.out";

    int N, M;
    const int MAX_N = 50000;
    const int max_edge_cost = 1000;
    const int MAX_BEST_COST = MAX_N * max_edge_cost;
    
    vector<vector<pair<int, int>>> adj_list;

    ifstream ifs(in_file);
    ifs >> N >> M;
    adj_list.resize(N + 1);

    for (int m = 1; m <= M; m++)
    {
        int u, v, c;
        ifs >> u >> v >> c;
        adj_list[u].push_back(make_pair(c, v));
    }
    ifs.close();

    set<pair<int, int>> Q;
    vector<int> best_cost;
    vector<char> in_queue;
    
    best_cost.resize(N + 1);
    in_queue.resize(N + 1);
    fill(best_cost.begin(), best_cost.end(), MAX_BEST_COST);
    best_cost[1] = 0;
    for (int u = 1; u <= N; u++)
        Q.insert(make_pair(best_cost[u], u));
    fill(in_queue.begin(), in_queue.end(), 1);

    while (!Q.empty())
    {
        // pop the node with the minimum cost from Q
        int u = Q.begin()->second;
        Q.erase(Q.begin());
        in_queue[u] = 0; //no longer in Q

        //parse the adjacency list
        for (auto& p : adj_list[u])
        {
            int v = p.second;
            int c = p.first;

            //only nodes still in the queue
            //the nodes no longer in queue already reached their minimum cost
            if (in_queue[v] == 1)
            {
                int cuv = best_cost[u] + c;
                if (cuv < best_cost[v])
                {
                    //remove the previous cost
                    Q.erase(make_pair(best_cost[v], c));
                    //update the minimum cost of the node v
                    best_cost[v] = cuv;
                    //insert the new cost
                    Q.insert(make_pair(cuv, v));
                }
            }
        }
    }

    //write the result to the file
    ofstream ofs(out_file.c_str());
    for (int u = 2; u <= N; u++)
        if (best_cost[u] != MAX_BEST_COST)
            ofs << best_cost[u] << " ";
        else
            ofs << 0 << " ";
    ofs.close();

    return 0;
}