#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

typedef pair<int, int> iPair;

struct Graph
{
    int V, E; 
    vector< pair<int, int> >* adj;

    Graph(int V, int E);  // Constructor 

    void addEdge(int u, int v, int w);
    void shortestPath(int s);
    void readEdges();
};

Graph::Graph(int V, int E)
{
    this->V = V;
    this->E = E;
    adj = new vector<iPair>[V];
}

void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back({ v, w });
    adj[v].push_back({ u, w });
}

void Graph::shortestPath(int src)
{
    // min heap with iPairs
    // first is minimum distance, second is the vertex label
    priority_queue< iPair, vector <iPair>, greater<iPair> > pq;
    // distances from root to every vertix
    vector<int> dist(V, INT_MAX);

    pq.push({ 0, src });
    dist[src] = 0;

    /* Looping till priority queue becomes empty (or all
      distances are not finalized) */
    while (!pq.empty())
    {
        // u is the vertex of minimum distance
        int u = pq.top().second;
        pq.pop();

        vector< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            int v = (*i).first;
            int weight = (*i).second;

            //  If there is shorted path to v through u. 
            if (dist[v] > dist[u] + weight)
            {
                // Updating distance of v 
                dist[v] = dist[u] + weight;
                pq.push({ dist[v], v });
            }
        }
    }


    for (int i = 1; i < V; ++i)
        fout<<dist[i] << " ";
}

void Graph::readEdges() {
    for (int i = 0; i < E; i++) {
        int u, v, w;
        fin >> u >> v >> w;
        // vertix count starts from 0
        addEdge(u-1, v-1, w);
    }
}

int main()
{

    int V, E ;
    fin >> V>> E;
    Graph g(V, E);

    g.readEdges();

    g.shortestPath(0);

    return 0;
}