#include <cstdio>
#include <vector>
#define NMAX 50005
#define INF 1000000
using namespace std;
FILE* fin=fopen("dijkstra.in","r");
FILE* fout=fopen("dijkstra.out","w");

int n,m;
vector < pair<int,int> > G[NMAX];
int dmin[NMAX],poz[NMAX],h[NMAX],k;
void citire();
void dijkstra();
void scriere();
void urca(int p);
void coboara(int p);
int main()
{
    citire();
    dijkstra();
    scriere();
    return 0;
}
void citire()
{
    int a,b,c;
    fscanf(fin,"%d %d",&n,&m);
    for (int i=0; i<m; i++)
    {
        fscanf(fin,"%d %d %d",&a,&b,&c);
        G[a].push_back(make_pair(b,c));
    }
}
void dijkstra()
{
    int i,minim;
    for (i=1; i<=n; i++) {dmin[i]=INF; poz[i]=-1;}
    poz[1]=1; dmin[1]=0;
    h[++k]=1;
    while (k) //cat timp exista elemente in heap
    {
        minim=h[1];
        h[1]=h[k--];
        poz[h[1]]=1;
        coboara(1); //cobor varful de pe pozitia 1

        for (i=0; i<G[minim].size(); i++)
        {
            if (dmin[G[minim][i].first]>dmin[minim]+G[minim][i].second)
            {
                dmin[G[minim][i].first]=dmin[minim]+G[minim][i].second;

                if (poz[G[minim][i].first]!=-1)
                    urca(poz[G[minim][i].first]);
                else
                {
                    h[++k]=G[minim][i].first;
                    poz[G[minim][i].first]=k;
                    urca(k);
                }
            }
        }
    }
}
void coboara(int p)
{
    int f,aux;
    while (p<=k)
    {
        f=p;
        if (p*2<=k)
        {
            f=p*2;
            if (f+1<=k && dmin[h[f]]>dmin[h[f+1]]) f++;
        }
        else return;
        if (dmin[h[p]]>dmin[h[f]])
        {
            poz[h[f]]=p;
            poz[h[p]]=f;
            aux=h[p];
            h[p]=h[f];
            h[f]=aux;
            p=f;
        }
        else return;
    }
    return;
}
void urca(int p)
{
    int t,aux;
    while (p>1)
    {
        t=p/2;
        if (dmin[h[p]]<dmin[h[t]])
        {
            poz[h[t]]=p; poz[h[p]]=t;
            aux=h[t];
            h[t]=h[p];
            h[p]=aux;
            p=t;
        }
        else p=1;
    }

}
void scriere()
{
    for (int i=2; i<=n; i++)
        if (dmin[i]!=INF) fprintf(fout,"%d ",dmin[i]);
        else fprintf(fout,"0 ");
    fprintf(fout,"\n");
}