using namespace std;
#include <fstream>
#include <vector>
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int Nmax = 50000;
const int INF = 99999999;

struct muchie{int vf, c;} aux;

vector<muchie> vec[Nmax+1];
int dmin[Nmax+1];
int heap[Nmax+1], nr = 0;

void push(int) ;
int get_min() ;


int main()
{
    int i, j, m, n, d, a, b, nod;
    vector<muchie>::iterator it;
    fin>>n>>m;
    for(i = 0; i < m; ++i)
    {
        fin >> a >> b >> d;
        aux.vf = b; aux.c = d;
        vec[a].push_back(aux);
    }
    push(1);
    for(i = 2; i <= n; ++i) {dmin[i] = INF; push(i);}
    
    while(nr)
    {
        nod = get_min();
        for(it = vec[nod].begin(); it != vec[nod].end(); ++it)
        {//toti vecinii varfului vf
            if(dmin[it->vf] > dmin[nod] + (it->c))
            {
                dmin[it->vf] = dmin[nod] + (it->c);
                push(it->vf);
            }
        }
    }
    for(i = 2; i <= n; ++i)
        if(dmin[i] == INF) fout << 0 << ' ';
        else fout << dmin[i] << ' ';
    fout << '\n';
    return 0;
}


void push(int nod)
{
    int poz = 1 + nr, aux;
    heap[++nr] = nod;
    while(poz > 1 && dmin[heap[poz]] < dmin[heap[poz / 2]])
        aux = heap[poz],
        heap[poz] = heap[poz / 2],
        heap[poz / 2] = aux,
        poz /= 2;
}


int get_min()
{
    int x = heap[1], aux, poz = 1;
    heap[1] = heap[nr]; heap[nr] = 0; --nr;
    while(poz <= nr / 2)
    {
        //stim ca poz are fiu stang
        if(2 * poz + 1 > nr)  //nu are fiu drept
        {
            if(dmin[heap[poz]] > dmin[heap[2*poz]])
                aux = heap[poz],
                heap[poz] = heap[2*poz],
                heap[2*poz] = aux;
            return x;
        }
        //are fiu drept
        if(dmin[heap[2*poz]] < dmin[heap[2*poz+1]])
        {
            if(dmin[heap[2*poz]] < dmin[heap[poz]])
                aux = heap[poz],
                heap[poz] = heap[2*poz],
                heap[2*poz] = aux,
                poz = 2*poz;
            else return x;
        }
        else
        {
            if(dmin[heap[2*poz+1]] < dmin[heap[poz]])
                aux = heap[poz],
                heap[poz] = heap[2*poz+1],
                heap[2*poz+1] = aux,
                poz = 2*poz+1;
            else return x;
        }
    }
    return x;
}