#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 X)
{
    int Son=(X<<1);
    if(Son+1<=Nheap && D[Heap[Son+1]]<D[Heap[Son]])
      Son++;
    if(Son<=Nheap && D[Heap[Son]]<D[Heap[X]])
        {
            Swap(Son,X);
            DownHeap(Son);
        }
}
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<<' ';
    }
}