#include<fstream>
#include<iostream>
#include<vector>
#define nmax 50003
#define maxx 999999999

using namespace std;

int heap[nmax], d[nmax], poz[nmax], n, m, nh;

vector < pair<int, int> >  l[nmax];

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



void read()
{
    int i, x, y, c;

    fin >> n >> m;

    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;

        l[x].push_back(make_pair(y, c));

    }
}




void swap(int i, int j)
{
    int aux;

    aux = heap[i];
    heap[i] = heap[j];
    heap[j] = aux;

    poz[heap[i]] = i;
    poz[heap[j]] = j;
}




void heapup(int k)
{
    if (k <= 1)
        return;

    int f = k / 2;

    if (d[heap[k]] < d[heap[f]])
    {
        swap(f, k);
        heapup(f);
    }

}





void heapdw(int k)
{
    int i = 2 * k;

    if (i <= nh)
    {
        if (i + 1 <= nh && d[heap[i + 1]] < d[heap[i]])
            i++;

        if (d[heap[i]] < d[heap[k]])
        {
            swap(i, k);
            heapdw(i);
        }

    }
}




int out_from_heap()
{
    swap(1, nh);
    poz[heap[nh]] = 0;
    nh--;

    return heap[nh + 1];
}




void dijkstra(int r)
{
    int i, p;

    for (i = 1; i <= n; i++)
    {
        d[i] = maxx;
        heap[i] = i;
        poz[i] = i;
    }

    d[r] = 0;
    nh = n;

    while (nh > 0)
    {
        p = out_from_heap();
        heapdw(1);


        for (i = 0; i < l[p].size(); i++)
        {

            if (d[l[p][i].first] > d[p] + l[p][i].second && poz[l[p][i].first])
            {
                d[l[p][i].first] = d[p] + l[p][i].second;

                heapup(poz[l[p][i].first]);
            }
        }
    }

}



void afis()
{
    int i;

    for (i = 2; i <= n; i++)
        if (d[i] < maxx)
            fout << d[i] << " ";
        else
            fout << "0 ";
}




int main()
{
    read();

    dijkstra(1);

    afis();

    fin.close();
    fout.close();

    return 0;
}