#include <iostream>
#include <fstream>
#include <iomanip>
#define oo 199999999
using namespace std;
int a[22003][22003], d[102], h[102], t[102], p[102];

ifstream f("dijkstra.in");
ifstream fout("dijkstra.out");

int fiu_d(int n)
{
    return 2*n+1;
}

int fiu_s(int n)
{
    return 2*n;
}

int tata(int n)
{
    return n/2;
}

void citire(int m)
{
    int i=0, x, y, c;
    while(i<m)
    {
        f >> x >> y >> c;
        a[x][y]=c;
        //a[y][x]=c;
        i++;
    }
}

void afisare_matrice(int n)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            cout << setw(3) << a[i][j] << " ";
        cout << endl;
    }
}

void umplere(int n)
{
    for(int i=1; i<=n; i++)
    {
        h[i]=i;
        p[i]=i;
        if(i>1)
            d[i]=oo;
    }
}

void schimbare(int &a, int &b)
{
    int aux=a;
    a=b;
    b=aux;
}

void coborare(int n, int k)
{
    int fiu;
    do
    {
        fiu=0;
        if(fiu_s(k) <= n)
        {
            fiu=fiu_s(k);
            if(fiu_d(k) <=n && d[h[fiu_d(k)]] < d[h[fiu_s(k)]])
                fiu=fiu_d(k);
            if(d[h[fiu]] > d[h[k]])
                fiu=0;
        }

        if(fiu)
        {
            schimbare(h[fiu], h[k]);
            schimbare(p[h[fiu]], p[h[k]]);
            k=fiu;
        }
    }
    while(fiu);
}

void urcare(int k)
{
    int contor;
    do
    {
        contor=0;
        if(tata(k)>0 && d[h[k]]<=d[h[tata(k)]])
        {
            schimbare(p[h[k]], p[h[tata(k)]]);
            schimbare(h[k], h[tata(k)]);
            k=tata(k);
            contor=1;
        }
    }
    while(contor);
}

void afisare(int n)
{
    for(int i=1; i<=n; i++)
        cout << h[i] << " ";
}

void afisare_p(int n)
{
    for(int i=1; i<=n; i++)
        cout << p[i] << " ";
}

void dijkstra_heap(int n)
{
    int nod, k=n;
    while(k>0)
    {
        nod=h[1];
        schimbare(h[k], h[1]);
        schimbare(p[h[k]], p[h[1]]);
        k--;
        coborare(k, 1);

        for(int i=1; i<=n; i++)
            if(a[nod][i] && d[i]>d[nod]+a[nod][i])
            {
                d[i]=d[nod]+a[nod][i];
                t[i]=nod;
                urcare(p[i]);
            }
    }
}

void drum(int k)
{
    if(t[k]) drum(k);
    cout << k << " ";
}

int main()
{
    int n, m, i;
    f >> n >> m;
    citire(m);
    //afisare_matrice(n);
    umplere(n);
    dijkstra_heap(n);
    for(i=2; i<=n; i++)
        fout << d[i] << " ";
    return 0;
}