#include <cstdio>
#include <vector>
#include <utility>
#define N 50005
using namespace std;
vector<pair<int,int> > v[N];
int n,m,i,L,x,y,c,d[N],h[N],p[N],oo=1<<30,viz[N];
void hd(int),hu(int),sw(int,int);
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[x]=1;
        for(vector<pair<int,int> >::iterator 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;
}