#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)
	
        {
	
            if(incoada[p->val])
	
            {
	
                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++)
	
    {
	
        if(dist[i] != oo)
	
            out<<dist[i]<<' ';
	
        else
	
            out<<0<<' ';
	
    }
	
}
	
 
	
int main()
	
{
	
    read();
	
    dijkstra();
	
    afis();
	
    return 0;
	
}