#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;} 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;
    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(),compara);
}
void dijkstra()
{
    int i,j,vfmin;
    hip aux;
    while(!Cmin.empty())
    {
        aux=Cmin.front();
        vfmin=aux.nod;
        pop_heap(Cmin.begin(),Cmin.end(),compara);
        Cmin.pop_back();
        for(j=0;j<L[vfmin].size();j++)
            if(Dmin[L[vfmin][j].vf]>Dmin[vfmin]+L[vfmin][j].cost)
            {
                Dmin[L[vfmin][j].vf]=Dmin[vfmin]+L[vfmin][j].cost;
                aux2.nod=L[vfmin][j].vf;
                aux2.cost= Dmin[L[vfmin][j].vf];
                Cmin.push_back(aux2);
                push_heap(Cmin.begin(), Cmin.end(),compara);
            }

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

}