#include<fstream>
using namespace std;
int n,D[100002],vfstart;
struct nod
{
    int cost,v;
    nod *urm;
};
nod *LA[100002];
int VIZ[100002],T[100002];
//D[i]= costul minim de la vfstart pana la i
void citire()
{
    int m,i,a,b,c;
    nod *p;
    ifstream fin ("dijKstra.in");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        p=new nod;
        p->v=b;
        p->cost=c;
        p->urm=LA[a];
        LA[a]=p;
    }
    fin.close();
}
void DIJKSTRA ()
{
    int i,j,vmin,poz;
    nod *p;
    vfstart=1;
    for(i=1;i<=n;i++)
    {
        D[i]=2000000000;
    }
    D[vfstart]=0;
    for(i=1;i<=n-1;i++)
    {
        vmin=2000000000;
        for(j=1;j<=n;j++)
        {
            if(D[j]<vmin&&VIZ[j]==0)
            {
                vmin=D[j];
                poz=j;
            }
        }
        if(vmin==2000000000)
        {
            break;
        }
        VIZ[poz]=1;
        //relaxare
        for(p=LA[poz];p!=0;p=p->urm)
        {
            j=p->v;
            if(D[j]>D[poz]+p->cost)
            {
                D[j]=D[poz]+p->cost;
                T[j]=poz;
            }
        }
    }
}
void afisare ()
{
    int i;
    ofstream fout("dijkstra.out");
    for(i=2;i<=n;i++)
    {
        if(D[i]==2000000000)
        {
            fout<<"0"<<" ";
        }
        else
        {
            fout<<D[i]<<" ";
        }
    }
    fout.close();
}
int main ()
{
    citire();
    DIJKSTRA();
    afisare();
    return 0;
}