#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define NMAX 50005
#define INF 200000200

vector < pair<int,int> > Graf[NMAX]; ///graful
int N, M, L;
int D[NMAX], ///D[x] = dist minima de la sursa la nodul x
Heap[NMAX * 2 + 100], ///Heap[x] = ordinul(al catelea in ord cronologica este) nodului de pe pozitia x in Heap
Poz[NMAX], ///Poz[x] = pozitia pe care se afla nodul cu ordinul x in Heap
Tata[NMAX]; ///T[x] = nodul de la care s-a ajuns la x

void push(int k) {  ///sift
    while( (k * 2 <= L && D[Heap[k]] > D[Heap[k * 2]]) || (k * 2 + 1 <= L && D[Heap[k]] > D[Heap[k * 2 +1 ]]) )
    {
        if (D[Heap[k * 2]] < D[Heap[k * 2 + 1]] || k * 2 + 1 > L)
        {
            swap(Heap[k],Heap[k * 2]);
            swap(Poz[Heap[k]],Poz[Heap[k * 2]]);
            k *= 2;
        }
        else
        {
            swap(Heap[k],Heap[k * 2 + 1]);
            swap(Poz[Heap[k]],Poz[Heap[k * 2 + 1]]);
            k = k * 2 + 1;
        }
    }
}

void pop(int k) {  ///percolate
    while(k > 1 && D[Heap[k]] < D[Heap[k / 2]])
    {
        swap(Heap[k], Heap[k / 2]);
        swap(Poz[Heap[k]], Poz[Heap[k / 2]]);
        k = k / 2;
    }
}

void introduce_in_heap(int nod)
{
    Heap[++L] = nod;
    Poz[nod] = L;
    pop(L);
}

int scoate_radacina_heap()
{
    int x = Heap[1];
    swap(Heap[1],Heap[L]);
    swap(Poz[Heap[1]],Poz[Heap[L]]);
    L--;
    push(1);
    Poz[x] = 0;
    return x;
}

void afis(int a[NMAX]) {
    for(int i = 1; i <= N; i++)
        g<<a[i]<<' ';
    g<<'\n';
}

int main()
{
    f>>N>>M;

    int i, x, y, c;

    for(i = 1; i <= M; i++) {
        f>>x>>y>>c;
        Graf[x].push_back(make_pair(y, c));
    }

    for(i = 1; i <= N; i++) D[i] = INF;
    D[1] = 0; /// distanta de la nodul 1 la celelalte noduri

    for(i = 0; i < Graf[1].size(); i++) {
        D[Graf[1][i].first] = Graf[1][i].second;
        Tata[Graf[1][i].first] = 1;
    }


    for(i = 2; i <= N; i++)
        introduce_in_heap(i);

    int k = N - 1;
    while(k) {
        int x = scoate_radacina_heap();

        for(i = 0; i < Graf[x].size(); i++) ///minimizarea drumului
            if(D[x] + Graf[x][i].second < D[Graf[x][i].first] && Poz[Graf[x][i].first])
            {
                D[Graf[x][i].first] = D[x] + Graf[x][i].second;
                Tata[Graf[x][i].first] = x;
                pop(Poz[Graf[x][i].first]); ///pornim percolate de la pozitia care o ocupa nodul y in Heap

            }

        k--;

    }

    for(i = 2; i <= N; i++)
        if(D[i] == INF) g<<"0 ";
        else g<<D[i]<<' ';
    g<<'\n';

    return 0;
}