#include <iostream>
#include <fstream>


#include <vector>
#include <set>


#define MAX_INT 999999

using namespace std;


//storing distances
int dist[MAX_INT];


vector< vector <pair<int, int> > > graph;


void addEdge(int a, int b, int c){
    graph[a].push_back(make_pair(b, c));
    graph[b].push_back(make_pair(a, c));
}

void shortestPath(int startNode, int n){

ofstream ki("dijkstra.out");

    set<pair<int, int> > minset;
    minset.insert(make_pair(0, startNode));
    dist[startNode] = 0;
    while(!minset.empty()){
        pair<int, int> temp = *(minset.begin());
        minset.erase(minset.begin());
        int currentNode = temp.second;
        for(int i = 0; i < graph[currentNode].size(); i++){
            int node = graph[currentNode][i].first;
            int weight = graph[currentNode][i].second;
            if(dist[node] > dist[currentNode] + weight){
                if(dist[node] != MAX_INT){
                    minset.erase(minset.find(make_pair(dist[node], node)));
                }
                dist[node] = dist[currentNode] + weight;
                minset.insert(make_pair(dist[node], node));
            }
        }
    }

    for(int i = 2; i < n; i++){
        ki << dist[i]<< " " ;
    }



}





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




    int n, m, a, b, c;


    be >> n >> m;



    vector< pair<int,int> > eVec;
    for(int i = 0; i < m; i++){
        graph.push_back(eVec);
        dist[i] = MAX_INT;
    }



   for(int i = 0; i < m; i++){
        be >> a >> b >> c;

        addEdge(a, b, c);
    }
    shortestPath(1, m);



}