#include <bits/stdc++.h>

#define INFINIT 50000000001
#define NMAX 50000

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

vector<pair<int, int> >G[NMAX + 1];
long long dist[NMAX + 1];
int H[NMAX + 1];
int heapPoz[NMAX + 1];
int dimHeap;

void sift(int poz){
    /*
        Cazuri:
        1) Am doar fiu in stanga
        -- Verific daca ma duc in stanga sau nu mai e nevoie deloc
        2) Am fiu in stanga si dreapta
        -- Verific care din ei e candidatul pt ce imi trebuie si verific daca trb sa ma duc in el
    */
    if(poz * 2 > dimHeap){
        return;
    }
    int leftSon = poz * 2;

    if(poz * 2 + 1 > dimHeap){
        ///Cazul 1
        if(dist[ H[leftSon] ] < dist[ H[poz] ]){
            swap(heapPoz[ H[leftSon] ], heapPoz[ H[poz] ]);
            swap(H[leftSon], H[poz]);
            sift(leftSon);
        }
        return;
    }

    ///Cazul 2:
    int rightSon = poz * 2 + 1;
    if(dist[ H[leftSon] ] <= dist[ H[rightSon] ]){
        ///ma duc prin stanga
        swap(heapPoz[ H[leftSon] ], heapPoz[ H[poz] ]);
        swap(H[leftSon], H[poz]);
        sift(leftSon);
    }
    else {
        ///ma duc prin dreapta
        swap(heapPoz[ H[rightSon] ], heapPoz[ H[poz] ]);
        swap(H[rightSon], H[poz]);
        sift(rightSon);
    }
}

int getHeapMin(){
    return H[1];
}

void deleteHeapMin(){
    swap(heapPoz[ H[1] ], heapPoz[ H[dimHeap] ]);
    swap(H[1], H[dimHeap]);
    dimHeap--;
    sift(1);
}

void percolate(int poz){
    if(poz == 1){
        return;
    }

    if(dist[ H[poz] ] < dist[ H[poz / 2] ]){
        swap(heapPoz[ H[poz] ], heapPoz[ H[poz / 2] ]);
        swap(H[poz], H[poz / 2]);
        percolate(poz / 2);
    }
}

inline void updateHeap(int poz){
    ///adica dist[ H[poz] ] a suferit o modificare; s-a micsorat
    ///adica are potential sa o ia in sus
    percolate(poz);
}

int main()
{
    int N, M;
    fin >> N >> M;
    for(int i = 1; i <= M; i++){
        int a, b, c;
        fin >> a >> b >> c;
        G[a].push_back({b, c});
    }

    dimHeap = N;
    for(int i = 1; i <= N; i++){
        dist[i] = INFINIT;
        H[i] = i;
        heapPoz[i] = i;
    }
    dist[1] = 0;
    //H[1] = 1;


    for(int times = 1; times <= N; times++){
        int node = getHeapMin();

        for(int i = 0; i < G[node].size(); i++){
            int vec = G[node][i].first;
            if(dist[node] + G[node][i].second < dist[vec]){
                dist[vec] = dist[node] + G[node][i].second;
                updateHeap(heapPoz[vec]);
            }
        }

        deleteHeapMin();
    }

    for(int i = 2; i <= N; i++){
        if(dist[i] == INFINIT){
            fout << 0;
        }
        else {
            fout << dist[i];
        }
        fout << ' ';
    }

    return 0;
}