#include <fstream>
#define infinit (1<<29)

using namespace std;

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

struct nod{
    int info;
    int cost;
    nod* leg;
};

nod *l[50001],*p;

int n,m,g,i,x,nody,y, d[50001], t[50001], poz[50001], h[50001];

inline void swapy(int i, int j)
{
    int x;
    x=h[i];
    h[i] = h[j];
    h[j] = x;
    x = poz[h[i]];
    poz[h[i]] = poz[h[j]];
    poz[h[j]] = x;
}

void heapup(int i)
{
    if(d[h[i/2]]<d[h[i]])
        return;
    swapy(i,i/2);
    heapup(i/2);
}

void heapdown(int i)
{
    int st,dr;
    if(i*2>m)
        return;
    st=d[h[i*2]];
    if(i*2+1<=m)
        dr = d[h[i*2+1]];
    else dr = st + 1;

    if(st<dr)
    {
        if(d[h[i]]<=st)
            return;
        swapy(i,2*i);
        heapdown(i*2);
    }
    else{
            if(d[h[i]] <= dr)
            return;

            swapy(i,i*2+1);
            heapdown(2*i+1);

               }
}



void Dijkstra(int sursa)
{
    int i;
    nod *p;
    m = n;
    for(i = 1; i <= n; ++i)
        {
            d[i] = infinit;
            poz[i] = i;
            h[i] = i;
        }
    d[sursa] = 0;
    d[0] = -1;

    for(i = 1; i <= n; ++i)
    {
        nody = h[1];
        swapy(1,m);
        --m;
        heapdown(1);
        for(p = l[nody]; p!= NULL; p=p->leg)
            if(d[p->info]>d[nody]+p->cost)
        {
            d[p->info] = d[nody] + p->cost;
            t[p->info] = nody;
            heapup(poz[p->info]);
        }
    }


}


int main()
{
    fin >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        fin >> x >> y >> g;
        p = new nod;
        p -> info = y;
        p -> leg = l[x];
        p -> cost = g;
        l[x] = p;

    }


    Dijkstra(1);

    for(i = 2; i <= n; ++i)
        if(d[i]!=infinit)
            fout << d[i] << " ";
        else fout << 0 << " ";

}