#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<int> distances(int source,vector<vector<pair<int,int> > > &graph,int numberOfNodes){
    vector<int> dist(numberOfNodes+1,1e9);
    dist[source] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > priorityQueue;
    priorityQueue.push({0,source});
    while(!priorityQueue.empty()){
        pair<int,int> currentNode = priorityQueue.top();
        priorityQueue.pop();
        for(auto vecin: graph[currentNode.second]){
            if(dist[vecin.first] > currentNode.second + vecin.second){
                dist[vecin.first] = currentNode.second + vecin.second;
                priorityQueue.push({dist[vecin.first],vecin.first});
            }
        }
    }
    return dist;

}
int main(){
    vector<vector<pair<int,int> > > graph;
    int numberOfNodes,numberOfEdges;
    fin >> numberOfNodes >> numberOfEdges;
    graph.resize(numberOfNodes + 1);
    for(int i=1;i<=numberOfEdges;i++){
        int nodeA,nodeB,distance;
        fin >> nodeA >> nodeB >> distance;
        graph[nodeA].push_back({nodeB,distance});
        //graph[nodeB].push_back({nodeA,distance});
    }
    vector<int> solution = distances(1,graph,numberOfNodes);
    for(int i=2;i<=numberOfNodes;i++){
        fout << solution[i] << " ";
    }



    return 0;
}