#include <algorithm>
#include <list>
#include <queue>
#include <iostream>
#include <fstream>
#define max_length 200001

using namespace std;

class Graf {

private:

    int noduri;
    int muchii;
    list<pair<int, int>>* memoryData;

public:

    Graf(int noduri, int muchii);

    void addEdge(int nod1, int nod2, int distanta);

    vector<int> dijkstra();

    void printDistance(vector<int>);


    virtual ~Graf() {
        // default empty
    };
};

Graf::Graf(int noduri, int muchii) {

    this->noduri = noduri;
    this->muchii = muchii;
    memoryData = new list<pair<int, int>>[noduri + 1];

}

void Graf::addEdge(int nod1, int nod2, int distanta) {

    memoryData[nod1].push_back(make_pair(nod2, distanta));
}

vector<int> Graf::dijkstra() {

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> priorityQueue;
    vector<int> distanta(noduri + 1, max_length);
    distanta[1] = 0;
    priorityQueue.push(make_pair(0, 1));

    while (!priorityQueue.empty()) {
        int nodSelectat = priorityQueue.top().second;
        priorityQueue.pop();

        list<pair<int, int> >::iterator i;
        for (i = memoryData[nodSelectat].begin(); i != memoryData[nodSelectat].end(); ++i) {
            if (distanta[i->first] > distanta[nodSelectat] + i->second) {
                distanta[i->first] = distanta[nodSelectat] + i->second;
                priorityQueue.push(make_pair(distanta[i->first], i->first));
            }
        }
    }
    return distanta;
}
void Graf::printDistance(vector<int> response) {
    ofstream fileout("dijkstra.out");
    for (int i = 2; i <= noduri; i++)
        fileout << ((response[i] != max_length) ? response[i] : 0) << " ";
}
int main()
{

    int noduri, muchii;
    int aux1, aux2, aux3;

    ifstream readData("dijkstra.in");

    readData >> noduri >> muchii;

    Graf* graf = new Graf(noduri, muchii);

    for (auto i = 1; i <= muchii; i++) {
        readData >> aux1 >> aux2 >> aux3;
        graf->addEdge(aux1, aux2, aux3);
    }
    readData.close();

    graf->printDistance(graf->dijkstra());

    return 0;
}