#include <cstdio>

using namespace std;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(make_pair(y,c));
    }
    for(i=1;i<=n;i++)
    {
        h[i]=p[i]=i;
        d[i]=oo;
    }
    d[1]=0;
    L=n;
    for(;L&&d[h[1]]<oo;)
    {
        x=h[1];sw(1,L);L--;hd(1);viz[h[1]]=1;
        for(it=v[x].begin();it!=v[x].end();it++)
        {
            if(viz[*it->first])continue;
            if(d[x]+*it->second<d[*it->first])
            {
                d[*it->first]=d[x]+*it->second;
                hu(p[*it->first]);
            }
        }
    }
    for(i=2;i<=n;i++)
        d[i]==oo?printf("0 "):printf("%d ",d[i]);
    return 0;
}
void hd(int tata)
{
    int fiu=2*tata;
    if(fiu>L)return;
    if(fiu<L)if(d[h[fiu]]>d[h[fiu+1]])fiu++;
    if(d[h[fiu]]<d[h[tata]]){sw(tata,fiu);hd(fiu);}
}
void hu(int fiu)
{
    int tata=fiu/2;
    if(!tata)return;
    if(d[h[fiu]]<d[h[tata]]){sw(tata,fiu);hu(tata);}
}
void sw(int i,int j)
{
    int aux=h[i];h[i]=h[j];h[j]=aux;
    p[h[i]]=i;p[h[j]]=j;
}