#include <cstdio>
#include <vector>

FILE* in;
FILE* out;

struct arc{
unsigned short nxt;
unsigned short val;
};

const int Q=50002;

std::vector<arc> v[Q];

int nrnod,nrarc;

int cost[Q],nviz;

int h[Q],nr,pozh[Q];

void schimb(int a, int b)
{
    int aux;

    aux=pozh[h[a]];
    pozh[h[a]]=pozh[h[b]];
    pozh[h[b]]=aux;

    aux=h[a];
    h[a]=h[b];
    h[b]=aux;
}

void coboara(int p)
{
    int act=p;

    if( cost[h[2*p]] < cost[h[act]] && 2*p<=nr)
        act=2*p;
    if( cost[h[2*p+1]] < cost[h[act]] && 2*p+1<=nr )
        act=2*p+1;

    if(act!=p)
    {
        schimb(act,p);
        coboara(act);
    }
}

void urca(int p)
{
    while(cost[h[p]]<cost[h[p/2]] && p!=1)
    {
        schimb(p,p/2);
        p/=2;
    }
}

void add(int x)
{
    h[++nr]=x;
    pozh[x]=nr;
    urca(nr);
}

void sterg(int x)
{
    int loc=pozh[x];
    schimb(nr,pozh[x]);
    nr--;
    coboara(loc);
    urca(loc);
}

void parcurgere()
{
    int act;
    while(nviz<nrnod)
    {
        act=h[1];
        sterg(h[1]);
        for(int i=0; i<v[act].size(); i++)
        {
            if(cost[v[act][i].nxt]>cost[act]+v[act][i].val)
            {
                sterg(v[act][i].nxt);
                cost[v[act][i].nxt]=cost[act]+v[act][i].val;
                add(v[act][i].nxt);
            }
            if(cost[v[act][i].nxt]==0)
            {
                nviz++;
                cost[v[act][i].nxt]=cost[act]+v[act][i].val;
                add(v[act][i].nxt);
            }
        }
    }
}

int main()
{
    in=fopen("dijkstra.in","r");
    out=fopen("dijkstra.out","w");

    fscanf(in,"%d %d",&nrnod,&nrarc);

    int a,b,c;

    for(int i=1; i<=nrarc; i++)
    {
        fscanf(in,"%d%d%d",&a,&b,&c);
        v[a].push_back(arc{b,c});
    }
    nviz=1;
    add(1);

    parcurgere();

    for(int i=2; i<=nrnod; i++)
        fprintf(out,"%d ",cost[i]);

    return 0;
}