#include <bits/stdc++.h>

#define N 50050

using namespace std;

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

const int infinite = 10000000000;

vector <pair <int, int> > nodes[N]; // {destination, cost}

priority_queue <pair <int, int> > Queue; // {cost, node}

int totalNodes;

int distances[N];

bool viz[N];

void readVariables(){

    int totalEdges;
    fin >> totalNodes >> totalEdges;
    for ( int origin, destination, cost; totalEdges; totalEdges-- ){

        fin >> origin >> destination >> cost;
        nodes[origin].push_back({destination, cost});
    }
}

void solveProblem(){

    for( int index = 2; index <= totalNodes; index++ )
        distances[index] = infinite;
    distances[1] = 0;

    Queue.push({0,1});
    viz[1] = 1;
    for ( int currentCost, currentNode ; Queue.size(); ){

        tie(currentCost, currentNode) = Queue.top();
        Queue.pop();
        currentCost *= -1;

//        if ( currentCost < distances[currentCost] )
//            continue; // useless distances;

        for ( auto it : nodes[currentNode] ){
            if ( distances[it.first] > currentCost+it.second ){

                distances[it.first] = currentCost+it.second;
                if(viz[it.first] == 0){
                    Queue.push({-distances[it.first], it.first});
                    viz[it.first] = 1;
                }
            }
        }
    }
}

inline void printSolution(void){

    for ( int index = 2; index <= totalNodes; index++ )
        fout << (distances[index] < infinite ? distances[index] : 0) << " ";
}

int main(){
    readVariables();
    solveProblem();
    printSolution();
}