#include <fstream>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int inf=1<<30;
const int nmax=50001;
const int mmax=250001;
int n,m,d[nmax],coada[mmax];
struct lista
{
    int c;
    int v;
    lista *urm;
};
lista *nou,*cap[nmax];
void dijkstra(int ns)
{   int i,j,nod,pi,ps,c,v;
    for(i=1;i<=n;i++)
    {   d[i]=inf;

    }
    d[ns]=0;
    pi=1;
    ps=1;
    coada[1]=ns;
    while(pi<=ps)
    {  nod=coada[pi]; nou=cap[nod];
        while(nou)
        {  c=nou->c;
            v=nou->v;
            if(d[v]>c+d[nod])
            {ps++;
            d[v]=c+d[nod];
            coada[ps]=v;

            }

            nou=nou->urm;
        }
        pi++;
    }

}
int main()
{   int i,a,b,c;
    in>>n>>m;
    for(i=1;i<=n;i++)
    {   in>>a>>b>>c;
        nou=new lista;
        nou->c=c;
        nou->v=b;
        nou->urm=cap[a];
        cap[a]=nou;


    }
    dijkstra(1);
    for(i=2;i<=n;i++)
       if(d[i]==inf)out<<0<<" "; else  out<<d[i]<<" ";
    return 0;
}