#include <iostream>
#include <fstream>
#define Nmax 50000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod
{
    int info,cost;
    nod *urm;
};
nod *a[Nmax];
int n,m;
void ADD (nod *&prim,int x,int c)
{
    nod *q=new nod;
    q->info=x;
    q->cost=c;
    q->urm=prim;
    prim=q;
}
void Citire ()
{   int i,x,y,c;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        ADD(a[x],y,c);
    }
}

void Dijkstra ()
{
    int viz[Nmax]={0},d[Nmax]={0},cap,minim,i,z,j;
    const int inf=999999999;
    nod *p;
    for (i=2;i<=n;i++) //initializez vectorul de distante
            d[i]=inf;
    for (p=a[1];p!=NULL;p=p->urm)
        d[p->info]=p->cost;
        viz[1]=1;
    for (i=1;i<n;i++) //calculez de n-1 un minim si verific daca se poate obtine un drum mai scurt spre celelalte prin intermediul lui
    {
        minim=inf;
        for (j=1;j<=n;j++)
        if (viz[j]==0&&d[j]<minim) {minim=d[j];cap=j;}
        viz[cap]=1;

        for (p=a[cap];p!=NULL;p=p->urm)
            if (viz[p->info]==0)
        {

            if (d[cap]+p->cost<d[p->info]) d[p->info]=p->cost+d[cap];
        }
    }
    for (i=2;i<=n;i++)
        fout<<d[i]<<" ";
}
int main()
{
    Citire();
    Dijkstra();

    return 0;
}