// https://www.infoarena.ro/problema/dijkstra

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

using namespace std;

struct Neighbour
{
    int vertex, cost;
};

class Graph
{
private:
    struct CompareCost
    {
        bool operator()(const Neighbour &a, const Neighbour &b) const
        {
            return a.cost > b.cost;
        }
    };

    static const int MAX_VERTICES = 200000;
    static const int MAX_EDGES = 400000;

    int noVertices;
    int noEdges;

    vector<vector<Neighbour>> neighbours;

    priority_queue<Neighbour, vector<Neighbour>, CompareCost> vertexQueue;
    // folosim priority queue pentru a gasi cel mai apropiat nod de nodul sursa
    // (nodul cu care am inceput Dijkstra)


    vector<int> costToSelectedVertex;
    // costul catre nodul selectat in Dijkstra (nodul sursa):
    // cost[i] = costul de la i la nodul selectat in Dijkstra SAU costul de la nodul selectat in Dijkstra la i


public:
    Graph(int noVertices, int noEdges)
        : noVertices(noVertices), noEdges(noEdges),
          neighbours(noVertices + 1)
    {
    }

    int getNoVertices()
    {
        return noVertices;
    }

    int getNoEdges()
    {
        return noEdges;
    }

    void addNeighbours(int vertex1, int vertex2, int cost)
    {
        neighbours[vertex1].push_back({vertex2, cost});
        neighbours[vertex2].push_back({vertex1, cost});
    }

    void addNeighbour(int vertex, int neighbour_to_add, int cost)
    {
        neighbours[vertex].push_back({neighbour_to_add, cost});
    }

    const vector<int>& calculateDijkstra(int startNode)
    {
        costToSelectedVertex = vector<int>(noVertices + 1, INT_MAX);
        costToSelectedVertex[startNode] = 0;

        for (Neighbour neigh : neighbours[startNode])
            vertexQueue.push(Neighbour{neigh.vertex, neigh.cost});


        while (!vertexQueue.empty())
        {
            Neighbour currEdge = vertexQueue.top();
            vertexQueue.pop();

            if (costToSelectedVertex[currEdge.vertex] != INT_MAX)
            {
                continue;
            }

            costToSelectedVertex[currEdge.vertex] = currEdge.cost;
            

            for (Neighbour neigh : neighbours[currEdge.vertex])
                if (costToSelectedVertex[neigh.vertex] == INT_MAX)
                    vertexQueue.push({neigh.vertex, currEdge.cost + neigh.cost});
        }



        for (int i=1; i <= noVertices; i++)
            if (costToSelectedVertex[i] == INT_MAX)
                costToSelectedVertex[i] = 0;

        return costToSelectedVertex;
    }
};



int main()
{
    int N, M;

    ifstream fin ("dijkstra.in");
    fin>> N >> M;
    Graph graph(N, M);

    for (int i=1; i<=M; i++)
    {
        int left, right, cost;
        fin >> left >> right >> cost;

        graph.addNeighbour(left, right, cost);
    }
    
    fin.close();


    const vector<int>& result = graph.calculateDijkstra(1);

    ofstream fout("dijkstra.out");

    for (int i=2; i <= N; i++)
        fout << result[i] << " ";
    fout << "\n";

    fout.close();

    return 0;
}