///DIJKSTRA
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> Node;

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

class Comp {public: bool operator () (Node& a, Node& b){return (a.second > b.second);}};

void dijkstra(vector<vector<Node> >& adjList, int start, vector<int>& answ) {
    priority_queue<Node, vector<Node>, Comp> heap;

    answ.assign(adjList.size(), INF);
    answ[start] = 0;

    heap.push(Node(start, answ[start]));

    int current;
    int currCost;
    vector<Node>::iterator it;

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



        for(it = adjList[current].begin(); it != adjList[current].end(); ++it)
            if(answ[it -> first] > currCost + it -> second) {
                answ[it -> first] = currCost + it -> second;
                heap.push(Node(it -> first, answ[it -> first]));
            }
    }
}

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

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

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

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

    vector<int> answ(N);
    dijkstra(adjList, 0, answ);

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

    return 0;
}