/*
     Pasi:

    Algoritmul trece o singura data prin toate nodurile.
    Trebuie sa am un priority queue de minime in care tin minte nodul si costul din predecesor in acesta.
    Vector de predecesori in parcurgere.

    Initial matricea de costuri pentru noduri este stata la infinit
    Pornesc din nodul A, setez d[A]=0 si vad ca pot relaxa cand costul nodului + muchia catre vecin < d[vecin]
    Daca da atunci setez d[vecin] = d[A] + muchia(A,vecin) si updatez predecesorul nodurilor relaxate ca fiind nodul curent
    Toti vecinii relaxati sunt pusi in minHeap.
    Dupa ce termin cu toti vecinii dau pop la radacina minHeapului, adica nodul cu cea mai mica distanta catre el.
    Incep iarasi sa ii verific vecinii

    Pentru a afla path-ul pornesc din nodul destinatie si o iau din tata in tata pana in nodul start.

*/

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge {
    int x, y, c;
};


const int NMAX = 10005;
int tata[NMAX];
vector<pair<int,int>> L[NMAX];
priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
int d[NMAX];
const int inf = 1e9;
int cost_curent;

void djk(const int start_node){
    d[start_node] = 0;
    tata[start_node] = -1;
    pq.push({d[start_node], start_node});

    while(!pq.empty()){
        int cost_curent = pq.top().first;
        int nod_curent = pq.top().second;
        pq.pop();

        if (cost_curent > d[nod_curent]) continue;


        for(const auto pair: L[nod_curent]){
            int cost_spre_vecin = pair.second;
            int vecin = pair.first;

            if(d[vecin] > cost_curent + cost_spre_vecin){
                d[vecin]= cost_curent + cost_spre_vecin;
                tata[vecin] = nod_curent;
                pq.push({d[vecin],vecin});
            }
        }
    }
}

int main(){
    int N, M, nod_start, nod_dest;
    cin >> N >> M;
    for(int i=1; i<=N;i++) d[i]=inf;

    // cout << "Nod start, nod destinatie: ";
    // cin >> nod_start >> nod_dest;

    for (int i=1; i<=M;i++) {
        Edge e;
        cin >> e.x >> e.y >> e.c;
        L[e.x].push_back({e.y, e.c});
    }
    djk(1);

    for (int i=2;i<=N;i++) {
        cout << d[i] <<  " ";
    }

    // cout << d[nod_dest]<< endl;
    //
    // int nod = nod_dest;
    // while (tata[nod]!=-1) {
    //     cout << nod << "->";
    //     nod = tata[nod];
    // }
    // cout << nod_start;
}