///DIJKSTRA HOME 04.01
///PUTOVITS
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <limits>

using namespace std;

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

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+1);

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

    vector<unsigned> minCost(N+1, MAXunsigned);

	//from Dijkstra function
    priority_queue<Edge, vector<Edge>, greater<Edge> > pq;
    pq.push(Edge(1, 0));

    minCost[1] = 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 + minCost[current] < minCost[it -> second]) {
                    minCost[it -> second] = it -> first + minCost[current];
                    pq.push(*it);
                }
        }
	}


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