#include<cstdio>
#include<vector>
#define N 50010
#define vec it->first
#define dis it->second
#define dst c[nod]
#define swapp aux=h[t];h[t]=h[f];h[f]=aux;p[h[f]]=f;p[h[t]]=t
using namespace std;
int n,m,x,y,z,h[N],p[N],c[N],i,lg,nod,oo=100000000;
vector<pair<int,int> > v[N] ;
vector<pair<int,int> >::iterator it;
void hu(int),hd(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,&z);
        v[x].push_back(make_pair(y,z));
    }
    for(i=1;i<=n;i++)
    {
        h[i]=p[i]=i;
        c[i]=oo;
    }
    lg=n;
    for(;lg;)
    {
        nod=h[1];if(c[nod]==oo) break;
        h[1]=h[lg];p[h[1]]=1;lg--;hd(1);
        for(it=v[nod].begin();it!=v[nod].end();it++)
            if(c[vec]>dis+dst)
            {
               c[vec]=dst+dis;
               hu(vec);
            }
    }
    for(i=2;i<=n;i++) c[i]==oo?printf("0 "):printf("%d ",c[i]);
    return 0;
}
void hd(int t)
{
    int aux,f=2*t;
    if(f>lg) return;
    if(f<lg) if(c[h[f+1]]<c[h[f]]) f++;
    if(c[h[t]]>c[h[f]]) {swapp;hd(f);}
}
void hu(int f)
{
    int aux,t=f/2;
    if(!t) return;
    if(c[h[t]]>c[h[f]]) {swapp;hu(t);}
}