#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax=50000;
const int oo=INT_MAX;

int N, M;
vector < pair<int, int> > G[Nmax+5];

int D[Nmax+5], H[Nmax+5][2], Heap_size=1; //prima col pt distanta, a doua pt index
bool use[Nmax+5];

int father(int nod)
{
    return nod/2;
}

int left_son(int nod)
{
    return nod*2;
}

int right_son(int nod)
{
    return nod*2+1;
}

int min()
{
    return H[1][1]; //indexul primului element din heap
}

void sift(int k)
{
    int son=0;
    do
    {
        if (left_son(k)<=N)
        {
            son=left_son(k);
            if (right_son(k)<=N && H[right_son(k)][0]>H[son][0])
                son=right_son(k);
        }

        if (H[son][0]>=H[k][0])
            son=0;
        else
        {
            swap(H[son][0], H[k][0]);
            swap(H[son][1], H[k][1]);
            k=son;
        }
    } while(son);
}

void percolate(int k)
{
    while (k>1 && H[k][0]<H[father(k)][0])
    {
        swap(H[k][0], H[father(k)][0]);
        swap(H[k][1], H[father(k)][1]);
        k=father(k);
    }
}

void cut()
{
    H[1][0]=H[Heap_size][0];
    H[1][1]=H[Heap_size][1];
    Heap_size--;
    if(Heap_size>0)
        sift(1);
}

void citire()
{
    fin >> N >> M;
    for (int i=1; i<=M; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }
}

void dijkstra(int start)
{
    for (int i=1; i<=N; i++)
        D[i]=oo;
    D[start]=0;
    H[1][0]=0; //distanta
    H[1][1]=1; //indexul

    for (int k=1; k<N; k++)
    {
        int nod=min();
        //cout << nod << " ";
        cut();

        for (int i=0; i<(int)G[nod].size(); i++)
        {
            int vecin=G[nod][i].first, cost=G[nod][i].second;
            D[vecin]=min(D[vecin], D[nod]+cost);

            Heap_size++;
            H[Heap_size][0]=D[vecin];
            H[Heap_size][1]=vecin;
//            for (int i=1; i<=Heap_size; i++)
//                cout << H[i] << " ";
//            cout << endl;
            percolate(Heap_size);
        }
    }
}

void afisare()
{
    for (int i=2; i<=N; i++)
    {
        if (D[i]==oo)
            D[i]=0;
        cout << D[i] << " ";
    }
    cout << "\n";
}

int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}