///DIJKSTRA HOME 04.01
///PUTOVITS

#include <fstream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const unsigned MAXunsigned = numeric_limits<unsigned>::max()/2;

typedef pair<unsigned, unsigned> Edge;


int main() {
    ifstream inStr("dijkstra.in");
    ofstream outStr("dijkstra.out");

    unsigned N, M;
    inStr >> N >> M;

    vector<vector<Edge> > adjList(N);

    unsigned from, to, cost;
    for(unsigned i=0; i<M; i++) {
        inStr >> from >> to >> cost;
        --from; --to;
        adjList[from].push_back(Edge(cost, to));
    }

    vector<unsigned> minCost(N, MAXunsigned);

	//from Dijkstra function
    priority_queue<Edge, vector<Edge>, greater<Edge> > pq;
    pq.push(Edge(0, 0));
    minCost[0] = 0;

    while(!pq.empty()) {
        unsigned current = pq.top().second;
        unsigned currCost = pq.top().first;
        pq.pop();

        if(currCost <= minCost[current]) {
            for(vector<Edge>::iterator it = adjList[current].begin(); it != adjList[current].end(); it++){
                if(it -> first + currCost < minCost[it -> second]) {
                    minCost[it -> second] = it -> first + currCost;
                    pq.push(Edge(minCost[it->second],it->second));
                }
            }
        }
	}


    for(unsigned i=1; i<N; i++)
        if(minCost[i] == MAXunsigned)
            outStr<<"0 ";
        else
            outStr << minCost[i] << ' ';
    outStr << '\n';
}