#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 50002
#define INF 10000000;
FILE *fin,*fout;
using namespace std;

struct muchie {int vf,cost;};
struct hip {int cost, nod;
            bool operator< (hip &xx) { return cost<xx.cost; }} aux2;
vector <muchie> L[NMAX];
vector <hip> Cmin;
void citire();
void initializare();
void dijkstra();
//bool compara (hip a, hip b) { return a.cost<b.cost;}
int n,m,Dmin[NMAX],M[NMAX];
int main()
{
    citire();
    initializare();
    dijkstra();
    fclose(fin); fclose(fout);
    return 0;
}
void citire()
{
    fin=fopen("dijkstra.in", "r"); fout=fopen("dijkstra.out", "w");
    int a,b,c,i;
    muchie aux;
    fscanf (fin, "%d%d", &n, &m);
    for(i=1;i<=m;i++)
    {
        fscanf (fin, "%d%d%d", &a, &b, &c);
        aux.vf=b;aux.cost=c;
        L[a].push_back(aux);
    }

}
void initializare()
{
    int i;
    for(i=1;i<=n;i++) Dmin[i]=INF;
    Dmin[1]=0;M[1]=1;
    for(i=0;i<L[1].size();i++)
    {
        Dmin[L[1][i].vf]=L[1][i].cost;
        aux2.cost=L[1][i].cost;
        aux2.nod=L[1][i].vf;
        Cmin.push_back(aux2);
    }
    make_heap(Cmin.begin(),Cmin.end());
}
void dijkstra()
{
    int i,j,vfmin,ax;
    hip aux;
    while(!Cmin.empty())
    {
        aux=Cmin.front();
        vfmin=aux.nod;
        pop_heap(Cmin.begin(),Cmin.end());
        Cmin.pop_back();
        M[vfmin]=1;
        for(j=0;j<L[vfmin].size();j++)
            if(!M[L[vfmin][j].vf])
            {
                ax=Dmin[vfmin]+L[vfmin][j].cost;
                if(Dmin[L[vfmin][j].vf]>ax)
                {
                    Dmin[L[vfmin][j].vf]=ax;
                    aux2.nod=L[vfmin][j].vf;
                    aux2.cost= Dmin[L[vfmin][j].vf];
                    Cmin.push_back(aux2);
                    push_heap(Cmin.begin(), Cmin.end());
                }
            }


    }
    for (i=2; i<=n; ++i)
        if (Dmin[i]!=10000000) fprintf (fout, "%d ", Dmin[i]); else fprintf (fout, "0 ");
    fprintf (fout, "\n");

}