#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);
    }
}
int Vecini (int x,int y)//verifica daca y se afla in lista lui x. Daca da, returneaza costul muchiei
{
    nod *p;
    for (p=a[x];p!=NULL;p=p->urm)
        if (p->info==y) return p->cost;
    return -1;
}
void Dijkstra ()
{
    int viz[Nmax]={0},d[Nmax]={0},cap,minim,i,z,j;
    const int inf=999999999;
    for (i=2;i<=n;i++) //initializez vectorul de distante
        {   z=Vecini(1,i);
            if (z!=-1) d[i]=z;
            else d[i]=inf;
        }
        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 (j=1;j<=n;j++)
            if (viz[j]==0)
        {
            z=Vecini(cap,j);
            if (z!=-1&&d[cap]+z<d[j]) d[j]=d[cap]+z;
        }
    }
    for (i=2;i<=n;i++)
        fout<<d[i]<<" ";
}
int main()
{
    Citire();
    Dijkstra();

    return 0;
}