///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[0] = 0;

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

        if(currCost == minCost[current]) {
            for(vector<Edge>::iterator 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(N, MAXINT);
    dijkstra(adjList, minCost);

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

    return 0;
}