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

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int Nmax = 50005, oo = 100000000;
int n, m, pos[Nmax], Heap[Nmax], D[Nmax], Nheap;
vector < pair <int, int> > G[Nmax];

void Swap(int a, int b)
{
    swap(pos[Heap[a]],pos[Heap[b]]);
    swap(Heap[a], Heap[b]);
}

void Downheap(int nod)
{
    int son = nod*2;
    if(son > Nheap) return;
    if(son == Nheap && D[Heap[son]] < D[Heap[nod]])
    {
        Swap(nod, son);
        return;
    }
    if(D[Heap[son]] < D[Heap[son+1]])
    {
        if(D[Heap[son]] < D[Heap[nod]])
        {
            Swap(nod, son);
            Downheap(son);
        }

    }
    else
    {
        if(D[Heap[son+1]] < D[Heap[nod]])
        {
            Swap(nod, son+1);
            Downheap(son+1);
        }
    }
}

void Upheap(int nod)
{
    int tata = nod/2;
    if(tata && D[Heap[nod]] < D[Heap[tata]])
    {
        Swap(tata, nod);
        Upheap(tata);
    }
}

int main()
{
    f>>n>>m;
    while(m--)
    {
        int x, y, c;
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    for(int i = 2; i <= n; i++) D[i] = oo;
    for(int i = 1; i <= n; i++)
    {
        Heap[i] = i;
        pos[i] = i;
    }
    Nheap = n;
    for(int i = 1; i <= n; i++)
    {
        int nod = Heap[1];
        Swap(1,Nheap--);
        Downheap(1);
        //urmeaza relaxarea
        for(int j = 0; j < (int)G[nod].size(); j++)
        {
            int vecin = G[nod][j].first;
            int cost = G[nod][j].second;
            if(D[vecin] > D[nod] + cost)
            {
                D[vecin] = D[nod] + cost;
                Upheap(pos[vecin]);
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if (D[i]!=oo)
            g<<D[i]<<' ';
        else
            g<<0<<' ';
    }
}