#include<fstream>
#include<vector>

using namespace std;

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

struct nodstruct
{
    int v,l;
};

const int NMAX = 50001;
const int INF = 500000001;

int d[NMAX], h[NMAX], poz[NMAX];
vector <nodstruct> v[NMAX];

int n,m,nh;

void adauga(int nod);
void urca(int p);
void schimba(int px, int py);
void sterge(int p);
void coboara(int p);

void adauga(int nod)
{
    nh++;
    h[nh] = nod;
    poz[nod] = nh;
    urca(nh);
}

void urca(int p)
{
    while(p > 1 && d[h[p / 2]] > d[h[p]])
    {
        schimba(p/2, p);
        p /= 2;
    }
}

void schimba(int px, int py)
{
    int aux = h[px];
    h[px] = h[py];
    h[py] = aux;

    poz[ h[px] ] = px;
    poz[ h[py] ] = py;

}

void sterge(int p)
{
    schimba(p , nh);
    nh--;
    coboara(p);
}

void coboara(int p)
{
     int fs = 2 * p, fd = 2 * p + 1, bun = p;

    if(fs <= nh && d[h[fs]] < d[h[bun]]) bun = fs;
    if(fd <= nh && d[h[fd]] < d[h[bun]]) bun = fd;

    if(p != bun)
    {
        schimba(p, bun);
        coboara(bun);
    }
}

void dijkstra(int nod)
{
    int i, dist, nod2;

    for(i=1; i<=n; i++)
        d[i] = INF;

    d[nod] = 0;
    poz[nod] = 1;
    adauga(nod);

    while(nh != 0)
    {
        nod = h[1];
        sterge(1);

        for(i = 0; i<v[nod].size(); i++)
        {
            nod2 = v[nod][i].v;
            dist = v[nod][i].l;

            if(d[nod] + dist < d[nod2])
            {
                d[nod2] = d[nod] + dist;

                if(poz[nod2] == 0)
                    adauga(nod2);
                else urca(poz[nod2]);
            }
        }
    }

}

void citire()
{
    int nod,vec,dist;

    f>>n>>m;

    for(int i=1; i<=m; i++)
    {
        f>> nod >> vec >> dist;
        v[nod].push_back( (nodstruct){vec, dist} );
    }
}

void afisare()
{
    for(int i=2; i<=n; i++)
    {
        if(d[i] == INF) g<< '0' << ' ';
        else g<< d[i] << ' ';
    }
}

int main()
{
    citire();
    dijkstra(1);
    afisare();

    return 0;
}