#include <fstream>
#define INF 0x3f3f3f3f
using namespace std;

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

typedef struct nod
{
    int inf,c;
    nod *urm;
} NOD;
typedef NOD *graf[50010];
graf G;

int n,m,d[50010],poz[50010],hh,aux[50010];
int h[50010];

void citire()
{
    f>>n>>m;
    int x,y,c;
    NOD *p;
    while(m--)
    {
        f>>x>>y>>c;
        p=new NOD;
        p->inf=y;p->urm=G[x];G[x]=p;p->c=c;
    }
    for(int i=1;i<=n;i++)
    {
        h[i]=i;
        d[i]=INF;
    }
    d[1]=0;
    hh=n;
}

void sift(int i)
{
    int ok=1;
    while(ok)
    {
        if(d[h[i]]>d[h[i*2]]&&i*2<=hh)
        {
            if(d[h[i]]>d[h[i*2+1]]&&i*2+1<=hh)
            {
                int aux=d[h[i*2]]<d[h[i*2+1]]?i*2:i*2+1;
                swap(h[i],h[aux]);
                i=aux;
            }
            else
            {
                swap(h[i],h[i*2]);
                i*=2;
            }
        }
        else
            if(d[h[i]]>d[h[i*2+1]]&&i*2+1<=hh)
            {
                swap(h[i*2+1],h[i]);
                i=i*2+1;
            }
            else
                ok=0;
    }
}

void percolate(int i)
{
    int ok=1;
    while(ok)
    {
        if(d[h[i]]<d[h[i/2]]&&i!=1)
        {
            swap(h[i],h[i/2]);
            i/=2;
        }
        else
            ok=0;
    }
    sift(i);
}

void del()
{
    h[1]=h[hh];
    sift(1);
}

void dijkstra()
{
    while(hh)
    {
        int x=h[1];
        del();
        hh--;
        for(NOD *i=G[x];i;i=i->urm)
            if(d[x]+i->c<d[i->inf])
            {
                d[i->inf]=d[x]+i->c;
                percolate(i->inf);
                for(int i=1;i<=hh;i++)
                    aux[i]=d[h[i]];
            }
        for(int i=1;i<=hh;i++)
                    aux[i]=d[h[i]];
    }
}
int main()
{
    citire();
    dijkstra();
    for(int i=2;i<=n;i++)
        if(d[i]==INF)
            g<<"0 ";
        else
            g<<d[i]<<' ';
    g<<'\n';
    return 0;
}