#include <bits/stdc++.h>

using namespace std;

const int dim = 50001;
const int oo = (int) (1e9);

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

struct no
{
    int val, l;
    no* urm;
};

no* lista[dim];
int n, m, l, coada[dim], poz[dim], nod[dim], dist[dim];
bool incoada[dim];

void adauga(int a, int b, int c)
{
    no* nou = new no;
    nou->val = b;
    nou->l = c;
    nou->urm = lista[a];
    lista[a] = nou;
}

int parinte(int i)
{
    return i / 2;
}

int stanga(int i)
{
    return 2 * i;
}

int dreapta(int i)
{
    return 2 * i + 1;
}

void pastreazaheap(int i)
{
    int st = stanga(i), dr = dreapta(i), mi;
    if(st <= l && coada[st] < coada[i])
        mi = st;
    else
        mi = i;
    if(dr <= l && coada[dr] < coada[mi])
        mi = dr;
    if(mi != i)
    {
        swap(coada[i], coada[mi]);
        swap(poz[nod[i]], poz[nod[mi]]);
        swap(nod[i], nod[mi]);
        pastreazaheap(mi);
    }
}

int minim()
{
    if(l < 1)
        return -1;
    int mi = coada[1];
    coada[1] = coada[l];
    int ret = nod[1];
    incoada[nod[1]] = false;
    swap(poz[nod[1]], poz[nod[l]]);
    swap(nod[1], nod[l]);
    l--;
    pastreazaheap(1);
    return ret;
}

void scade(int i, int val)
{
    if(val > coada[i])
        return;
    coada[i] = val;
    while(i > 1 && coada[parinte(i)] > coada[i])
    {
        swap(coada[parinte(i)], coada[i]);
        swap(poz[nod[i]], poz[nod[parinte(i)]]);
        swap(nod[i], nod[parinte(i)]);
        i = parinte(i);
    }
}

void inserare(int no, int val)
{
    l++;
    coada[l] = oo;
    incoada[no] = true;
    poz[no] = l;
    nod[l] = no;
    scade(l, val);
}

void read()
{
    in>>n>>m;
    int a, b, c;
    for(int i = 1;i <= m;i++)
    {
        in>>a>>b>>c;
        adauga(a, b, c);
    }
}

void dijkstra()
{
    int curent;
    dist[1] = 0;
    inserare(1, 0);
    for(int i = 2;i <=n;i++)
    {
        dist[i] = oo;
        inserare(i, dist[i]);
    }

    while(l)
    {
        curent = minim();
        for(no* p = lista[curent];p;p = p->urm)
        {
            int alt = dist[curent] + p->l;
            if(alt < dist[p->val])
            {
                dist[p->val] = alt;
                scade(poz[p->val], alt);
            }
        }
    }
}

void afis()
{
    for(int i = 2;i <= n;i++)
        out<<dist[i]<<' ';
}

int main()
{
    read();
    dijkstra();
    afis();
    return 0;
}