#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
vector<vector<pair<int, int>>> adj;
vector<int> shortest_dist;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> unmarked_nodes;
int nr_nodes, nr_edges;


void Dijkstra(const int &start_node = 1)
{
    unmarked_nodes.push({0, start_node});
    shortest_dist[start_node] = 0;

    while (!unmarked_nodes.empty())
    {
        int cur_vertex = unmarked_nodes.top().second;
        int dist_from_start_node = unmarked_nodes.top().first;
        unmarked_nodes.pop();

        if (dist_from_start_node != shortest_dist[cur_vertex])
        {
            continue;
        }

        for (const auto &_adj_vertex : adj[cur_vertex])
        {
            int adj_vertex = _adj_vertex.first;
            int weight = _adj_vertex.second;

            if (shortest_dist[cur_vertex] + weight < shortest_dist[adj_vertex])
            {
                shortest_dist[adj_vertex] = shortest_dist[cur_vertex] + weight;
                unmarked_nodes.push({shortest_dist[adj_vertex], adj_vertex});
            }
        }
    }
}


int main()
{
    ifstream fin("dijkstra.in");

    fin >> nr_nodes >> nr_edges;
    adj.resize(nr_nodes + 1);
    shortest_dist.resize(nr_nodes + 1, INF);
    
    while (nr_edges--)
    {
        int i, j, weight;
        fin >> i >> j >> weight;

        adj[i].push_back({j, weight});
    }

    Dijkstra();

    ofstream fout("dijkstra.out");
    for (int node = 2; node <= nr_nodes; ++node)
    {
        fout << (shortest_dist[node] == INF ? -1 : shortest_dist[node]) << " ";
    }
}