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

using namespace std;

const int MAXINT = numeric_limits<int>::max();

typedef pair<int, int> Edge;

struct Compare {bool operator () (Edge& a, Edge& b) {return a.second > b.second;}};

void dijkstra(vector<vector<Edge> >& adjList, vector<int>& minCost) {
    priority_queue<Edge, vector<Edge>, Compare> pq;
    pq.push(Edge(0, 0));

    minCost.assign(adjList.size(), MAXINT);
    minCost[0] = 0;

    int current, currCost;
    vector<Edge>::iterator it;
    while(!pq.empty()) {
        current = pq.top().first;
        currCost = pq.top().second;
        pq.pop();

        if(currCost > minCost[current])
            continue;

        for(it = adjList[current].begin(); it != adjList[current].end(); it++)
            if(it -> second + minCost[current] < minCost[it -> first]) {
                minCost[it -> first] = it -> second + minCost[current];
                pq.push(*it);
            }
    }
}

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

    int N, M;
    inStr >> N >> M;

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

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

    vector<int> minCost;
    dijkstra(adjList, minCost);

    for(int i=1; i<N; i++)
        if(minCost[i] == MAXINT)
            outStr << 0 << ' ';
        else
            outStr << minCost[i] << ' ';
    outStr << '\n';

    return 0;
}