#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

#define INF 999999999

int  m, n, nh,nr, h[100], d[100],urm[100],pred[100],poz[100], lst[100], vf[100], c[100];
//h are elementele din heap
//c are costurile citite
//d are costurile minime
//p are pozitia lui in heap
//lst pe ce pozitie incepe lista succesorilor lui x
//vf e extremitatea finala; ex: x are poz p, vf[x]=y, c[x] = costul muchiei de la x la y

void adauga(int x,int y,int drum)
{
    //adauga pe y in lista lui x si costul lor
    nr++;
    vf[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
    c[nr]=drum;
}

void schimb(int p, int q)
{
    int aux=h[p];
    h[p]=h[q];
    h[q]=aux;
    poz[h[p]]=p;
    poz[h[q]]=q;
}

void urca(int p)
{
    while(p>1 && d[h[p]]<d[h[p/2]])
    {
        schimb(p,p/2);
        p/=2;
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1, bun=p;
    if(fs<=nh && d[h[fs]]<d[h[bun]])
        bun=fs;
    if(fd<=nh && d[h[fd]]<d[h[bun]])
        bun=fd;
    if(bun!=p)
    {
        schimb(bun,p);
        coboara(bun);
    }
}

void sterge(int p)
{
    schimb(p,nh);
    nh--;
    urca(p);
    coboara(p);
}

int main()
{
    int i,drum,x,y,p;
    fin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        fin>>x>>y>>drum;
        adauga(x,y,drum);
    }
    nh=n;
    for(i=1;i<=n;i++)
    {
        h[i]=i;
        poz[i]=i;
    }
    d[1]=0;
    for(i=2;i<=n;i++)
        d[i]=INF;
    while(nh!=0)//nh scade in sterge()
    {
        x=h[1];
        sterge(1);
        poz[x]=-1; //-1 inseamna ca nu mai e in heap
        p=lst[x];
        while(p!=0)
        {
            y=vf[p];
            if(d[x]+c[p]<d[y])
            {
                d[y]=d[x]+c[p];
                pred[y]=x;
                urca(poz[y]);
            }
            p=urm[p];
        }
    }

    for(i=2;i<=n;i++)
        cout<<d[i]<<" ";
}