#include <algorithm>
#include <list>
#include <queue>
#include <iostream>
#include <bitset>
#include <limits>
#include <fstream>
#define INFINITY 200001

using namespace std;

class Graf {

private:

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

public:


    Graf() {
        // default empty;
    };

    Graf(int noduri, int muchii);

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

    void dijkstra();

    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::insert(int nod1, int nod2, int distanta) {

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

void Graf::dijkstra() {

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> priorityQueue;       
    vector<int> distanta(noduri+1, INFINITY);
    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));
            }
        }
    }
    ofstream fileout("dijkstra.out");
    for (int i = 2; i <= noduri; i++)
        fileout << ((distanta[i] != INFINITY) ? distanta[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->insert(aux1, aux2, aux3);
    }
    readData.close();

    graf->dijkstra();

    return 0;
}